Reputation: 1691
I've been working on understanding foldl
vs foldr
vs foldl'
in Haskell. I understand that the consensus is to use foldr
when f
is lazy in its second argument, as it mirrors the structure of the list. foldl'
is better when we know that the entire list needs to be processed and f
is strict in its arguments.
I'm specifically interested in a situation like this:
foldr (&&) False (repeat False)
returns False
.
But:
foldl (&&) False (repeat False)
never completes.
The foldr
expands to:
False && (False && (False && .... (False && *False*)) ... )
Whereas foldl
:
&& (... (&& (&& *False* False) False) ...) False
The stars are the base case False
passed into fold
.
Is foldr
able to terminate immediately because the LHS is just a single False
, while foldl
the single False
is all the way on the right, and it doesn't 'check' that until it's completed processing the left hand side?
Upvotes: 5
Views: 1647
Reputation: 1899
foldr op z [1..]
creates an expression tree like this:
op
/\
1 op
/\
2 op
/\
3 .
.
.
All but a finite part of that tree is below any particular op
, so if any of the op
s discard their arguments (or even just their second argument), the tree is reduced to a finite size, which can be completely evaluated in a finite time.
foldl op z [1..]
creates an expression tree like this:
.
.
.
op
/\
op 3
/\
op 2
/\
z 1
All but a finite part of that tree is above any particular op
, so even if every op
discards both of its arguments, no finite number of reduction steps can shrink it to a finite size.
If the lists are finite, then the trees' shapes are simply mirror images of each other, but the trees constructed from infinite lists don't have that symmetry, because infinite lists don't have that symmetry: they are infinite on the right, not on the left.
Upvotes: 3
Reputation: 60463
Let's look at the relevant definitions (not exactly the same as the ones from the Prelude, but equivalent for this analysis).
(&&) :: Bool -> Bool -> Bool
True && x = x
False && _ = False
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Look at the opportunities that each of foldr
and foldl
have to yield a result. They both yield a result immediately when given []
. In the (x:xs)
case, foldr
also has the opportunity to yield a result if f
returns immediately without evaluating its right argument (which is the recursive call). foldl
does not have this, since its outermost call is to itself, so the only time foldl
can give any information back is in the []
case, which is never reached for an infinite list.
In examples like this, I find it helpful to do some manual evaluation. Recall that Haskell's evaluation order goes outside-in: we evaluate as little as possible to get to an applicable pattern match of the outermost function application. I will italicize the next function to be evaluated in each step. foldr
is simple:
foldr (&&) False (repeat False) = foldr (&&) False (False : repeat False) = False && foldr (&&) False (repeat False) = False
And foldl
reveals the problem:
foldl (&&) False (repeat False) = foldl (&&) False (False : repeat False) = foldl (&&) (False && False) (repeat False) = foldl (&&) (False && False) (False : repeat False) = foldl (&&) ((False && False) && False) (repeat False) = foldl (&&) ((False && False) && False) (False : repeat False) = foldl (&&) (((False && False) && False) && False) (repeat False)
and so on. Notice that even if (&&)
had the ability to simplify by checking either side, we would still never get the opportunity to return it since we never reach the []
case.
However, the order that (&&)
evaluates its arguments does still matter (it evaluates the left one first, determined by pattern matching semantics). We can flip
the order of the arguments and see what foldr
does:
ghci> foldr (flip (&&)) False (repeat False)
^CInterrupted
(exercise) Why is this?
Upvotes: 11