Lists can be represented as:

data [a] = [] | a : [a]

Consider the following functions:

 foldl :: (b -> a -> b) -> b -> [a] -> b
 foldr :: (a -> b -> b) -> b -> [a] -> b

These two functions are used for what we call folding over a list. What does it mean by folding? In a broad sense, we can say that folds give us the power to evaluate a list by applying an operator between the list elements. First examples that come to mind can be finding the sum on a list of integers, append the elements of a list, etc. To fold, we also need a default value when we come to evaluate the end of list, or over an empty list, hence a seed value. Take a closer look at the type signatures, we can say that folds are much more powerful than these examples, as they also give us the power to change not only the structure of the list, but also the type of list.

Both foldl and foldr take a seed value of type b, a list of type a, and a function (let’s call it f). We can notice that foldl and foldr are only different with regards to f. foldl takes the seed value b and applies it to the head of the list, foldr takes the seed value b and applies f to the end of the list. Let’s see how.

Fold behaviour using examples

Suppose we have a list, and we need to sum over this list. Finding the sum means running over the whole list and adding the elements using (+) operator.

 let x = 1 : 2 : 3 : Nil
 foldl (+) 0 x = ((((0 + 1) + 2 ) + 3 ) + Nil)
 foldr (+) 0 x = (1 + (2 + (3 + (Nil + 0))))

While it all looks ok, what stands out is applying (+) on Nil. How is that supposed to behave? Let’s assume for now that (+) of an operand with Nil equals to that operand:

 x = 1 : 2 : 3 : Nil
 foldl (+) 0 x = ((((0 + 1) + 2 ) + 3 ) + Nil) = (((1 + 2) + 3 ) + Nil) = ((3 + 3) + Nil) = (6 + Nil) = 6
 foldr (+) 0 x = (1 + (2 + (3 + (Nil + 0)))) = (1 + (2 + (3 + 0))) = (1 + (2 + 3)) = (1 + 5) = 6

A few more examples: product = foldr (*) 1 or product = foldl (*) 1 length = foldr (const (+1)) 0 or length = foldl (const (1+)) 0 Both foldl and foldr produce the same answers.

Let’s implement both these functions to gain some more insights into their behaviour:

 foldl :: (b -> a -> b) -> b -> [a] -> b
 foldl f z Nil = z
 foldl f z (h : t) = foldl f (f z h) t

 foldr :: (a -> b -> b) -> b -> [a] -> b
 foldr f z Nil = z
 foldr f z (h : t) = f h (foldr f z t)

Jotting down the key features here: foldl is

• lazy (Haskell is lazy by default),
• tail recursive (the function f is applied first, and the recursive call is made later, in foldl f (f z h) t),
• left associative (consider the example above: (((0 + 1) + 2 ) + 3 ) ) foldr is
• lazy (nothing is evaluated until result is needed),
• not tail recursive (recursive call to foldr is made first, and then f is applied on top of it, in f h (foldr f z t))
• right associative (consider the example above: (1 + (2 + (3 + 0))) )

Too lazy to fold infinitely

Now I am going to apply folds on an infinite list and see what happens. Wait what? Obviously, if we call any fold on infinity it’s bound to overflow, right? But hey! we just forgot, that these folds are lazy. This means, that folds will only evaluate the list unless the result is actually needed. So if we have a function such as find:

 findl :: (a -> Bool) -> [a] -> Bool
 findl p = foldr (\a b -> if p b then True else a) False

 findr :: (a -> Bool) -> [a] -> Bool
 findr p = foldr (\a b -> if p a then True else b) False

Observe that the arguments are reversed for findl and findr. Now let’s try to run these:

 >> findr even [1..]
 >> True
 >> findl even [1..]
 ^CInterrupted

Observe that while find using foldr gives an answer, but foldl doesn’t. But should that’s how it should be with infinite list? What kind of magic is this foldr doing?? Well, it’s no magic but laziness. The foldr is simply not doing much. Let’s have a look at foldl and foldr implementations again:

 foldl f z (h : t) = foldl f (f z h) t
 foldr f z (h : t) = f h (foldr f z t)

While foldl first makes the recursive call, foldr first applies the function f and then recursively calls itself. But in our case of find, the f here is a boolean function. So if f h = True, then it need not go into evaluating the entire list! But such is not the case with the poor foldl. Before even applying f, foldl needs to recursively call itself (in a way keep looping…). Therefore, foldl cannot use f until it has worked out its entire nested expression. And hence, foldr is always the recommended way of folding. The thing to remember here is that laziness works for infinite lists when the second argument to the combining function is lazy. That’s why findr is possible but not (+). If we remove laziness from the picture, then both the arguments to the function need to be evaluated immediately, and then it won’t matter if we are calling foldl or foldr. Actually it would matter a bit, as foldl is tail recursive, and thus would be more efficient.

Did not care to read the big para before? let’s point what we learnt:

• both foldl and foldr use a combining function having 2 arguments.
• if the combining function is lazy in its second argument, foldr evaluates for infinite lists, whereas foldl doesn’t.
• This is because foldl is implemented in such a way that it has to first construct the entire expression before evaluation, hence stack overflows.
• If foldl is made strict (there is a foldl'), then as tail recursive is more efficient, it can be used to improve the performance of the code.
• Hence, foldr is the recommended way of folding, in order to preserve lazyness across function composition.
• However for strict languages, foldl seems a more natural choice.

What all can be folded

Till now we are seeing list being folded into a single value, but folds are not restricted to end into a single value. They can be anything as long as the type signatures match! There is something special about foldr if we take a different perspective. Till now we consider foldr as ‘folding from the right’, which, well, is like that. Let’s look again at our foldr example:

 for the list 1 : 2 : 3 : Nil
 foldr f z x = 1 `f` 2 `f` 3 `f` z

The similarity is quite striking! for every foldr operation, the cons (:) operator is replaced by infix f and Nil is replaced by z. This is what we call constructor replacement. Therefore, we can use foldr for actually replacing the list constructor.

map

Let’s try mapping over a list using fold:

 map f = foldr _f _z

Let’s now fill in _f :: (a -> b -> b). For mapping over a list, we do not need to change the structure of the list. Hence, we need (:). But just (:) is not sufficient. So at any point of time, if we are dealing with an element a, then we need it to be first transformed into b and then appended to the rest of the list as before. Voila! _f = ((:) . f). Here, (.) operator is called compose, where f . g is equivalent to \x -> f (g x). Next we need a default value for mapping a list in place of _z. What can be the default value for a list? Well, it’s Nil. Hence:

 map = foldr ((:) . f) Nil

filter

Similarly, let’s think about applying filter :: (a -> Bool) -> [a] -> [a]

 filter p = foldr _f _z

Here, yet again, a list remains a list hence _z = Nil. Now think about _f. For filtering a list, at any point of time, if we have an element a, for it to go in the list we need to check if it satisfies the predicate p and then if it does we add it else we don’t. So _f = \a b -> if p a then (a : b) else b. Hence:

 filter = foldr (\a b -> if p a then (a : b) else b) Nil

append

Let’s make it more challenging. What about appending two lists? i.e. implementing (++) :: [a] -> [a] -> [a]

 (++) xs ys = foldr _f _z

so what should be the ending/default value _z? For appending two lists together, we need that in Nil of first list, we get the second list. Hence _z = ys:

 (++) xs ys = foldr (:) ys xs

To write this in point-free notation, flip the args: (++) = flip (foldr (:))

I have dedicated a whole post to fold coz folds are not only widely used, for me they were the first steps into functional programming. Knowing the power of folds eabled me to write implementations of a lot of more functions in a crisp manner (Before that I was pattern matching for everything). I am a merrier fp programmer now that I have folded!