user2666425
user2666425

Reputation: 1691

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

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

Answers (2)

benrg
benrg

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 ops 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

luqui
luqui

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

Related Questions