Why does foldr work with infinite lists in Haskell but foldl doesn't?
I am working on understanding foldl
vs foldr
vs foldl'
in Haskell. I understand that it is a consensus to use foldr
when f
lazy in the second argument as it reflects the structure of the list. foldl'
it is better when we know that the entire list needs to be processed, but f
is strict in its arguments.
I am especially interested in this situation:
foldr (&&) False (repeat False)
returns False
.
But:
foldl (&&) False (repeat False)
never ends.
foldr
expands to:
False && (False && (False && .... (False && *False*)) ... )
Whereas foldl
:
&& (... (&& (&& *False* False) False) ...) False
Stars are the base register False
passed to fold
.
Is it foldr
possible to terminate immediately because the LHS is just one False
while the foldl
only one False
is on the right, and it doesn't "check" it while it has finished processing the left side?
source to share
Look at the relevant definitions (not exactly the same as those 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 foldr
and foldl
must give results. Both of them produce results immediately when given []
. In case (x:xs)
foldr
also has the ability to give a result if it f
returns immediately without evaluating its right argument (which is a recursive call). foldl
does not have this, since its an external call for itself, so the only time foldl
can give any information back in a case []
that is never reached for an infinite list.
In such examples, I find it helpful to do a manual assessment. Recall that the order of evaluation of Haskell is out-of-bounds: we evaluate as little as possible to get a good match for the outer function's application pattern. I will make the following function in italics, which will be evaluated at each step. foldr
simple:
foldr (&&) False ( repeat False) = foldr (&&) False (False: repeat False) = False && foldr (&&) False (repeat False) = False
And it 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)
etc. Note that even if we (&&)
had the opportunity to simplify by checking both sides, we still never get the opportunity to return it, since we never get to the case []
.
However, the order that (&&)
evaluates its arguments still matters (it evaluates to the left first, determined by pattern matching semantics). We can flip
order the arguments and see what does foldr
:
ghci> foldr (flip (&&)) False (repeat False)
^CInterrupted
(exercise) Why is this?
source to share