patternMinor
What type of formal notation is being used here to represent functional algorithms?
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
In this one, I'm not sure what the
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.
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:
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) \\ bsCode 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) \\ bsContext
StackExchange Computer Science Q#11707, answer score: 5
Revisions (0)
No revisions yet.