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

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