Why does foldr work on infinite lists in Haskell but foldl doesn't?

Question

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?

Answer 1

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?