HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What type of formal notation is being used here to represent functional algorithms?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
herewhatrepresentformalusedbeingtypealgorithmsnotationfunctional

Problem

Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design. I have experience with a number of programming languages, but my only experience with functional programming is in Scala. I understood that I would have to pick-up Standard ML and Haskell from the description of the book, but when I started reading the first section, I wasn't familiar with some of the operators being used.

Here are some examples of function definitions from the first chapter of the book (free to preview on Amazon):

I have seen "^" and "v" used to represent "and" and "or," but some of the other syntax (like False (0,n)) still throws me off.

In this one, I'm not sure what the accumArray(+)... is referring to. I'm thinking it's like a fold method using addition, but I don't understand the rest of the line.

Here, the author has done a good job of describing that \\ is set difference and the two vertical lines crossed with a horizontal one is union. However, I've never seen anything like that union symbol before.

I don't want to know what each of these examples means as much as I want to know what library of formal representation is Bird using to represent these algorithms, and also, if a specific programming language (Haskell/SML?) syntax is being used as well in conjunction with these special symbols.

Solution

The language is pretty-printed Haskell.

In regular source code, it would look like this:

checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0, n)
               (zip (filter ( Array Int Int
countlist xs = accumArray (+) 0 (0, n) (zip xs (repeat 1))

(as ++ bs) \\ cs = (as \\ cs) ++ (bs \\ cs) -- Not actual code
as \\ (bs ++ cs) = (as \\ bs) \\ cs
(as \\ bs) \\ cs = (as \\ cs) \\ bs

Code Snippets

checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0, n)
               (zip (filter (<= n) xs) (repeat True))
               where n = length xs

countlist :: [Int] -> Array Int Int
countlist xs = accumArray (+) 0 (0, n) (zip xs (repeat 1))

(as ++ bs) \\ cs = (as \\ cs) ++ (bs \\ cs) -- Not actual code
as \\ (bs ++ cs) = (as \\ bs) \\ cs
(as \\ bs) \\ cs = (as \\ cs) \\ bs

Context

StackExchange Computer Science Q#11707, answer score: 5

Revisions (0)

No revisions yet.