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

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.

• What exactly about False (0, n) for example throws you off? – phant0m May 1 '13 at 18:25
• By the way, False (0, n) is not a subexpression. False and (0, n) are two values, given as arguments to accumArray. – C. A. McCann May 1 '13 at 18:39
• @phant0m coming from my programming experience, it looked like there was a method called False that was taking two parameters: 0 and n. But C. A. McCann cleared up the misunderstanding. – David Kaczynski May 1 '13 at 18:57
• @DavidKaczynski: I suspected that was some of the confusion. Haskell functions take one argument at a time and function application is written as juxtaposition. Here, accumArray is being applied to four arguments--a "logical or" function, the boolean value False, a 2-tuple (pair) of Ints that appear to be array bounds, and a list of (Int, Bool) pairs filtered so the Ints are valid array indices (the whole second line). The where clause just defines n as the length of the input list within the scope of the function body. – C. A. McCann May 1 '13 at 19:10
• @DavidKaczynski: Also, you are correct in thinking this is a sort of fold. I assume it's using this accumArray function, which the documentation describes pretty clearly. – C. A. McCann May 1 '13 at 19:14

In regular source code, it would look like this:

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

• I'm going to accept this answer because the ASCII translation put it in terms that I better understand. Well, time for me to start learning Haskell. Cheers! – David Kaczynski May 1 '13 at 19:01
• @DavidKaczynski No problem, note that I just fixed a mistake: It needs to be (||), not (or) which is the same as or which is wrong ;) – phant0m May 1 '13 at 19:02

I haven't read the book but the snapshot is definitely Haskell. Most texts that contain Haskell code use some kind of pretty printer, most likely lhs2TeX. It assigns more type-setting-friendly symbols to many standard Haskell infix operations such as ++ or <=.

I suggest you to use browse Haskell's Prelude module, which contains functions available to all Haskell programs by default. Or you can search for a particular function using Hoogle.

• The biggest giveaway is the use of :: for type annotations. That's unique to Haskell and languages derived from it that borrow its syntax in full. – C. A. McCann May 1 '13 at 18:34