Folds are fundamental operations in functional programming. There are two basic types of linear folds: left folds and right folds. Superficially, they sound like symmetric versions of one another. In reality, the difference between them is important but subtle.
Consider a list: [1,2,3]. In Haskell, this is syntactic sugar for 1:(2:(3:[])). Right folds are simple: they replace all occurrences of the cons operator : with some operator `f`, and the empty list [] with some initial value z.
Let the symbol ~~ mean “is equivalent to”.
foldr f z [1,2,3] ~~ 1 `f` (2 `f` (3 `f` z))
Example: (sum of a list)
foldr (+) 0 [1,2,3] ~~ 1 + (2 + (3 + 0)) ~~ 6
Example: (identity)
foldr (:) [] [1,2,3] ~~ 1 : (2 : (3 : [])) ~~ [1,2,3]
Implementing foldr recursively is straightforward. As usual, we trust the function to do the right thing for a reduced part of the input. In this case, we trust that foldr makes the appropriate substitutions for just the tail of the input list. If we are trying to get from 1:(2:(3:[])) to 1 `f` (2 `f` (3 `f` z)), we trust that foldr f z (2:(3:[])) indeed gives 2 `f` (3 `f` z)). Then we can set foldr f z (1:(2:(3:[]))) to be 1 `f` (foldr f z (2:(3:[]))). In general, we define the induction step as:
foldr f z (x:xs) = x `f` (foldr f z xs)
Note that in each recursive call of foldr, the second parameter is not altered. This is not the case for left folds.
Now consider the base case. By successively taking the tail of a list, we will eventually reach the empty list. In that case, by definition, the result should be z:
foldr _ z [] = z
Left folds are more difficult to understand. Intuitively, if foldr produces 1 `f` (2 `f` (3 `f` z)), then foldl produces ((1 `f` 2) `f` 3) `f` z. If `f` is associative, then these are equivalent. In particular, + is associative, but : is not. To express left fold in Haskell, it is easiest to start with a specific case and then generalize. One of the canonical examples of a left fold is reverse, which reverses a given list. It would be reasonable to guess that we could define reverse recursively, using the form:
reverse [] = []
reverse (x:xs) = ___ reverse ___
However, if you stare at this for long enough, you will see that it is a dead end. When we assume that the subcall to reverse returns the correct result for some reduced part of the input, the only reasonable candidate is the tail xs. This does not help, as we cannot easily append to a list. Instead, we need an accumulator: another parameter on which to recurse in order to keep track of the intermediate result.
reverse = aux [] where
aux acc [] = acc
aux acc (x:xs) = aux (x:acc) xs
We start with an empty accumulator. At each inductive step, we advance along the input list and cons an element to the accumulator. Eventually, we reach the end of the input, at which point the accumulator holds exactly the result that we want and we return it all the way up the chain.
To get foldl, we generalize away from the cons operator in (x:acc), replacing it with a more general `f`.
foldl _ acc [] = acc
foldl f acc (x:xs) = foldl (acc `f` x) xs
Note the order of the operands of `f`. This is to obtain the same linear order as foldr. In particular:
reverse = foldl (flip (:)) []
reverse corresponds naturally to foldl, as the identity function on lists corresponds naturally to foldr. From this, we can intuit the fact that foldr works on infinite lists whereas foldl does not. After all, what would be the meaning of reverse [1..]? Interestingly, head $ reverse $ reverse [1..] does not work. Why? Left as an exercise for the reader.