Learn You a Haskell for Great Good! - Miran Lipovaca [34]
Right Folds with foldr
The right fold function, foldr, is similar to the left fold, except the accumulator eats up the values from the right. Also, the order of the parameters in the right fold’s binary function is reversed: The current list value is the first parameter, and the accumulator is the second. (It makes sense that the right fold has the accumulator on the right, since it folds from the right side.)
The accumulator value (and hence, the result) of a fold can be of any type. It can be a number, a Boolean, or even a new list. As an example, let’s implement the map function with a right fold. The accumulator will be a list, and we’ll be accumulating the mapped list element by element. Of course, our starting element will need to be an empty list:
map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs
If we’re mapping (+3) to [1,2,3], we approach the list from the right side. We take the last element, which is 3, and apply the function to it, which gives 6. Then we prepend it to the accumulator, which was []. 6:[] is [6], so that’s now the accumulator. We then apply (+3) to 2, yielding 5, and prepend (:) that to the accumulator. Our new accumulator value is now [5,6]. We then apply (+3) to 1 and prepend the result to the accumulator again, giving a final result of [4,5,6].
Of course, we could have implemented this function with a left fold instead, like this:
map' :: (a -> b) -> [a] -> [b]
map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs
However, the ++ function is much slower than :, so we usually use right folds when we’re building up new lists from a list.
One big difference between the two types of folds is that right folds work on infinite lists, whereas left ones don’t!
Let’s implement one more function with a right fold. As you know, the elem function checks whether a value is part of a list. Here’s how we can use foldr to implement it:
elem' :: (Eq a) => a -> [a] -> Bool
elem' y ys = foldr (\x acc -> if x == y then True else acc) False ys
Here, the accumulator is a Boolean value. (Remember that the type of the accumulator value and the type of the end result are always the same when dealing with folds.) We start with a value of False, since we’re assuming the value isn’t in the list to begin with. This also gives us the correct value if we call it on the empty list, since calling a fold on an empty list just returns the starting value.
Next, we check if the current element is the element we want. If it is, we set the accumulator to True. If it’s not, we just leave the accumulator unchanged. If it was False before, it stays that way because this current element is not the one we’re seeking. If it was True, it stays that way as the rest of the list is folded up.
The foldl and foldr1 Functions
The foldl1 and foldr1 functions work much like foldl and foldr, except that you don’t need to provide them with an explicit starting accumulator. They assume the first (or last) element of the list to be the starting accumulator, and then start the fold with the element next to it. With that in mind, the maximum function can be implemented like so:
maximum' :: (Ord a) => [a] -> a
maximum' = foldl1 max
We implemented maximum by using a foldl1. Instead of providing a starting accumulator, foldl1 just assumes the first element as the starting accumulator and moves on to the second one. So all foldl1 needs is a binary function and a list to fold up! We start at the beginning of the list and then compare each element with the accumulator. If it’s greater than our accumulator, we keep it as the new accumulator; otherwise, we keep the old one. We passed max to foldl1 as the binary function because it does exactly that: takes two values and returns the one that’s larger. By the time we’ve finished folding our list, only the largest element remains.
Because they depend on the lists they’re called with having at least