Learn You a Haskell for Great Good! - Miran Lipovaca [35]
Note
When making a fold, think about how it acts on an empty list. If the function doesn’t make sense when given an empty list, you can probably use a foldl1 or foldr1 to implement it.
Some Fold Examples
To demonstrate how powerful folds are, let’s implement some standard library functions using folds. First, we’ll write our own version of reverse:
reverse' :: [a] -> [a]
reverse' = foldl (\acc x -> x : acc) []
Here, we reverse a list by using the empty list as a starting accumulator and then approaching our original list from the left and placing the current element at the start of the accumulator.
The function \acc x -> x : acc is just like the : function, except that the parameters are flipped. That’s why we could have also written reverse' like so:
reverse' :: [a] -> [a]
reverse' = foldl (flip (:)) []
Next, we’ll implement product:
product' :: (Num a) => [a] -> a
product' = foldl (*) 1
To calculate the product of all the numbers in the list, we start with 1 as the accumulator. Then we fold left with the * function, multiplying each element with the accumulator.
Now we’ll implement filter:
filter' :: (a -> Bool) -> [a] -> [a]
filter' p = foldr (\x acc -> if p x then x : acc else acc) []
Here, we use an empty list as the starting accumulator. Then we fold from the right and inspect each element. p is our predicate. If p x is True—meaning that if the predicate holds for the current element—we put it at the beginning of the accumulator. Otherwise, we just reuse our old accumulator.
Finally, we’ll implement last:
last' :: [a] -> a
last' = foldl1 (\_ x -> x)
To get the last element of a list, we use a foldl1. We start at the first element of the list, and then use a binary function that disregards the accumulator and always sets the current element as the new accumulator. Once we’ve reached the end, the accumulator—that is, the last element—will be returned.
Another Way to Look at Folds
Another way to picture right and left folds is as successive applications of some function to elements in a list. Say we have a right fold, with a binary function f and a starting accumulator z. When we right fold over the list [3,4,5,6], we’re essentially doing this:
f 3 (f 4 (f 5 (f 6 z)))
f is called with the last element in the list and the accumulator, then that value is given as the accumulator to the next-to-last value, and so on.
If we take f to be + and the starting accumulator value to be 0, we’re doing this:
3 + (4 + (5 + (6 + 0)))
Or if we write + as a prefix function, we’re doing this:
(+) 3 ((+) 4 ((+) 5 ((+) 6 0)))
Similarly, doing a left fold over that list with g as the binary function and z as the accumulator is the equivalent of this:
g (g (g (g z 3) 4) 5) 6
If we use flip (:) as the binary function and [] as the accumulator (so we’re reversing the list), that’s the equivalent of the following:
flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6
And sure enough, if you evaluate that expression, you get [6,5,4,3].
Folding Infinite Lists
Viewing folds as successive function applications on values of a list can give you insight as to why foldr sometimes works perfectly fine on infinite lists. Let’s implement the and function with a foldr, and then write it out as a series of successive function applications, as we did with our previous examples. You’ll see how foldr works with Haskell’s laziness to operate on lists that have infinite length.
The and function takes a list of Bool values and returns False if one or more elements are False; otherwise, it returns True. We’ll approach the list from the right and use True as the starting accumulator. We’ll use && as the binary function, because we want to end up with True only if all the elements are True. The && function returns False if either of its parameters is False, so if we come across an element in the list that is False, the accumulator will be set as False and the final result will