The recursion for foldr f x ys
where ys = [y1,y2,...,yk]
looks like
f y1 (f y2 (... (f yk x) ...))
whereas the recursion for foldl f x ys
looks like
f (... (f (f x y1) y2) ...) yk
An important difference here is that if the result of f x y
can be computed using only the value of x
, then foldr
doesn't' need to examine the entire list. For example
foldr (&&) False (repeat False)
returns False
whereas
foldl (&&) False (repeat False)
never terminates. (Note: repeat False
creates an infinite list where every element is False
.)
On the other hand, foldl'
is tail recursive and strict. If you know that you'll have to traverse the whole list no matter what (e.g., summing the numbers in a list), then foldl'
is more space- (and probably time-) efficient than foldr
.
How fold
s differ seems to be a frequent source of confusion, so here's a more general overview:
Consider folding a list of n values [x1, x2, x3, x4 ... xn ]
with some function f
and seed z
.
foldl
is:
- Left associative:
f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
- Tail recursive: It iterates through the list, producing the value afterwards
- Lazy: Nothing is evaluated until the result is needed
- Backwards:
foldl (flip (:)) []
reverses a list.
foldr
is:
- Right associative:
f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
- Recursive into an argument: Each iteration applies
f
to the next value and the result of folding the rest of the list.
- Lazy: Nothing is evaluated until the result is needed
- Forwards:
foldr (:) []
returns a list unchanged.
There's a slightly subtle point here that trips people up sometimes: Because foldl
is backwards each application of f
is added to the outside of the result; and because it is lazy, nothing is evaluated until the result is required. This means that to compute any part of the result, Haskell first iterates through the entire list constructing an expression of nested function applications, then evaluates the outermost function, evaluating its arguments as needed. If f
always uses its first argument, this means Haskell has to recurse all the way down to the innermost term, then work backwards computing each application of f
.
This is obviously a far cry from the efficient tail-recursion most functional programmers know and love!
In fact, even though foldl
is technically tail-recursive, because the entire result expression is built before evaluating anything, foldl
can cause a stack overflow!
On the other hand, consider foldr
. It's also lazy, but because it runs forwards, each application of f
is added to the inside of the result. So, to compute the result, Haskell constructs a single function application, the second argument of which is the rest of the folded list. If f
is lazy in its second argument--a data constructor, for instance--the result will be incrementally lazy, with each step of the fold computed only when some part of the result that needs it is evaluated.
So we can see why foldr
sometimes works on infinite lists when foldl
doesn't: The former can lazily convert an infinite list into another lazy infinite data structure, whereas the latter must inspect the entire list to generate any part of the result. On the other hand, foldr
with a function that needs both arguments immediately, such as (+)
, works (or rather, doesn't work) much like foldl
, building a huge expression before evaluating it.
So the two important points to note are these:
foldr
can transform one lazy recursive data structure into another.
- Otherwise, lazy folds will crash with a stack overflow on large or infinite lists.
You may have noticed that it sounds like foldr
can do everything foldl
can, plus more. This is true! In fact, foldl is nearly useless!
But what if we want to produce a non-lazy result by folding over a large (but not infinite) list? For this, we want a strict fold, which the standard libraries thoughfully provide:
foldl'
is:
- Left associative:
f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
- Tail recursive: It iterates through the list, producing the value afterwards
- Strict: Each function application is evaluated along the way
- Backwards:
foldl' (flip (:)) []
reverses a list.
Because foldl'
is strict, to compute the result Haskell will evaluate f
at each step, instead of letting the left argument accumulate a huge, unevaluated expression. This gives us the usual, efficient tail recursion we want! In other words:
foldl'
can fold large lists efficiently.
foldl'
will hang in an infinite loop (not cause a stack overflow) on an infinite list.
The Haskell wiki has a page discussing this, as well.
Best Answer
Some explanations are in order!
What is the id function for? What is the role of? Why should we need it here?
id
is the identity function,id x = x
, and is used as the equivalent of zero when building up a chain of functions with function composition,(.)
. You can find it defined in the Prelude.In the above example, id function is the accumulator in the lambda function?
The accumulator is a function that is being built up via repeated function application. There's no explicit lambda, since we name the accumulator,
step
. You can write it with a lambda if you want:Or as Graham Hutton would write:
foldr's prototype is foldr :: (a -> b -> b) -> b -> [a] -> b
A Haskell programmer would say that the type of
foldr
is(a -> b -> b) -> b -> [a] -> b
.and the first parameter is a function which need two parameters, but the step function in the myFoldl's implementation uses 3 parameters, I'm complelely confused
This is confusing and magical! We play a trick and replace the accumulator with a function, which is in turn applied to the initial value to yield a result.
Graham Hutton explains the trick to turn
foldl
intofoldr
in the above article. We start by writing down a recursive definition offoldl
:And then refactor it via the static argument transformation on
f
:Let's now rewrite
g
so as to float thev
inwards:Which is the same as thinking of
g
as a function of one argument, that returns a function:Now we have
g
, a function that recursively walks a list, apply some functionf
. The final value is the identity function, and each step results in a function as well.But, we have handy already a very similar recursive function on lists,
foldr
!This looks like a very similar recursive scheme to our
g
function. Now the trick: using all the available magic at hand (aka Bird, Meertens and Malcolm) we apply a special rule, the universal property of fold, which is an equivalence between two definitions for a functiong
that processes lists, stated as:So, the universal property of folds states that:
where
g
must be equivalent to the two equations, for somek
andv
:From our earlier foldl designs, we know
v == id
. For the second equation though, we need to calculate the definition ofk
:Which, substituting our calculated definitions of
k
andv
yields a definition of foldl as:The recursive
g
is replaced with the foldr combinator, and the accumulator becomes a function built via a chain of compositions off
at each element of the list, in reverse order (so we fold left instead of right).This is definitely somewhat advanced, so to deeply understand this transformation, the universal property of folds, that makes the transformation possible, I recommend Hutton's tutorial, linked below.
References