3
$\begingroup$

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):

weird syntax

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.

more weird syntax

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.

kinda weird

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ What exactly about False (0, n) for example throws you off? $\endgroup$
    – phant0m
    May 1, 2013 at 18:25
  • 4
    $\begingroup$ By the way, False (0, n) is not a subexpression. False and (0, n) are two values, given as arguments to accumArray. $\endgroup$
    – C. A. McCann
    May 1, 2013 at 18:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – David Kaczynski
    May 1, 2013 at 18:57
  • $\begingroup$ @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. $\endgroup$
    – C. A. McCann
    May 1, 2013 at 19:10
  • $\begingroup$ @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. $\endgroup$
    – C. A. McCann
    May 1, 2013 at 19:14

2 Answers 2

Reset to default
5
$\begingroup$

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 (<= 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
Improve this answer
$\endgroup$
2
  • $\begingroup$ 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! $\endgroup$
    – David Kaczynski
    May 1, 2013 at 19:01
  • $\begingroup$ @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 ;) $\endgroup$
    – phant0m
    May 1, 2013 at 19:02
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – C. A. McCann
    May 1, 2013 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.