Monthly Archives: December 2014

The higher-order function ‘fold’

When students encounter higher-order functions in functional programming, they are normally exposed to the following three first: map, filter, and fold. The higher-order functions map and filter are intuitively accessible. With the former you apply a function to each element of a list, while the latter retains only elements for which a given predicate is true. One might want to implement those functions in Haskell as follows:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
  | p x       = x : filter p xs
  | otherwise = filter p xs

On the other hand, fold is somewhat more confusing. As I’ve found, the treatment of this topic on the Haskell wiki is not overly accessible to novices, while the explanation given in Learn You A Haskell is, like pretty much everything in it, too cute for its own good.

There are two cases of fold, namely foldr and foldl, with ‘r’l and ‘l’ describing right-associativity and left-associativity, respectively. One possible definition of foldr is:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

‘z’ is the last element of the list you’re applying the function to. I sometimes hear people refer to this as the “identity element”, but this is not necessarily correct. ‘z’ can be the identity element. For instance, if you want to multiply all values in a list of integers, you would chose the integer 1 to take the place of ‘z’. However, nothing is keeping you from picking any other integer.

To illustrate foldr with an example, let’s evaluate the following function call:

foldr (*) 1 [1,2,3]
(*) 1 (foldr (*) 1 [2,3])
(*) 1 ((*) 2  (foldr (*) 1 [3]))
(*) 1 ((*) 2  ((*) 3 (foldr (*) 1 [])))
(*) 1 ((*) 2  ((*) 3 1))
(*) 1 ((*) 2  3)
(*) 1 6

To make this evaluation more digestible from the fourth line onwards, it could also be written as:

1 * (2 * (3 * 1))
1 * (2 * 3)
1 * 6

This example shows the application of the function to each element in the list. Maybe this reminds you of how lists are constructed using the cons operator, i.e. (1 : (2 : (3 : []))) is represented, after adding syntactic sugar, as [1, 2, 3].

In fact, a list can be constructed using a fold. So, if you were in a silly mood, you could create a function that takes a list, runs it through fold, and returns the same list:

listId :: [a] -> [a]
listId xs = foldr (:) [] xs

Of course, ‘xs’ can be omitted on both sides of this equation. If you now call this function with the argument [1, 2, 3], you’ll get (1 : (2 : (3 : []))) in return, which is [1, 2, 3].

Let’s now look at foldl, which is fold with left-associativity. One possible definition is as follows.

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl _ z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

Evaluating the same expression as given above, with foldr, results in:

foldl (*) 1 [1,2,3]
foldl (*) ((*) 1 1) [2, 3]
foldl (*) ((*) ((*) 1 1) 2) [3]
foldl (*) ((*) ((*) ((*) 1 1) 2) 3) []
((*) ((*) ((*) 1 1) 2) 3)
((*) ((*) 1 2) 3)
((*) 2 3)

You can probably see why defining a ‘listId’ function with foldl results in an error.

Also note that foldl and foldr only give the same result if the binary operator f is associative. Just consider what happens when you’re using an operator that isn’t, for instance:

> foldr (/) 1 [1,2,3]
> 1.5
> foldl (/) 1 [1,2,3]
> 0.16666666666666666

The first function call evaluates to (1 / (2 / (3 / 1))), and the second to (((1 / 2) / 3) / 1).

Review: Introduction to Functional Programming (edX)

I just finished the last problem set in Erik Meijer’s online course Introduction to Functional Programming. This seems like a good opportunity to briefly reflect on it. There aren’t a lot of functional programming MOOCs available. I’m only aware of two Coursera courses, one on FP in Scala, and another on FRP in Akka. While Erik Meijer repeatedly made the point that his course was not on Haskell but on FP in general, there most certainly was a strong focus on exploring functional programming with Haskell.

The recommended course literature was Graham Hutton’s Programming in Haskell, which is incidentally the same book I used when I took a similar course at university. As far as programming-related textbooks go, Hutton’s book is among the best, as he explains topics concisely, and poses carefully selected exercises to the reader. It’s the exact opposite of your typical Java or Python textbook, or the, in my opinion, highly overrated “Learn you a (Haskell|Erlang) for Great Good” books, but that may be a topic for another article.

If you just used the textbook, you’d be well-prepared for the homework exercises and labs already. Still, I enjoyed Erik Meijer’s presentation, and his sometimes quirky remarks, such as that he wants his students to “think like a fundamentalist and code like a hacker”. In special “jam sessions” he demonstrated functional programming concepts in other languages, such as Scala, Dart, Hack, and Kotlin. What I also liked was that some of the labs were offered in several programming languages. The very first lab was offered in Haskell, Groovy, F#, Frege (!), and Ruby, for instance, which led me to playing around with some new languages.

This course is certainly, for the most part, comparable to a university-level course in functional programming. I do have some gripes with the form of the assessment, though. For instance, a common type of question asked you to indicate which of a given number of alternative function definitions were valid. Sometimes the code was obfuscated, and since you couldn’t just copy and paste it, it could easily happen that a GHCi error message was due to a mistake you made while copying the program. This might not have been a problem if those questions had been rare, but because there were so many of them, the tedium was palpable. In later weeks I skipped those questions since I saw very little educational value in them.

Further, the labs were a bit too straight-forward for my taste, but that may be a limitation of the MOOC format. The advice “follow the types” was repeated like a mantra. It is of course a good idea to use type signatures as a guide. However, being given a template that contains correct type signatures and that only requires one to write a few lines of code — if I’m not mistaken, in some weeks the labs required just about a dozen lines of Haskell in total — seems partly misguided. Obviously, it is much more difficult to design a program yourself, and define the correct type signatures. Merely filling in function definitions, on the other hand, is somewhat akin to painting by numbers. It might therefore be a good idea to add a peer-reviewed project to this course in its next iteration. My experience with peer-review on MOOCs is mixed, but it’s better than nothing. After all, the theory behind FP is sufficiently covered. It’s just that the course doesn’t require writing a lot of code, which could only be excused on the labs that focus on type classes and monads.

Overall, Introduction to Functional Programming is a very good course. However, if you’re taking it as a novice, you might want to do the exercises in Hutton’s book in order to get more practice with programming in Haskell.