Why `foldl1` runs out of memory yet `foldr1` works just fine?

Question

I wrote last function by using foldl1 and foldr1.

lastr :: [a] -> a
lastr = foldr1 (flip const)

lastl :: [a] -> a
lastl = foldl1 (flip const)

They just work fine for short lists. But when I tried with a very long list, [1..10^8], lastr returns the solution in 6.94 sec yet lastl ran out of memory.

Definition of foldr1 and foldl1 are (to my understanding)

foldr1 f [x] = x
foldr1 f (x:xs) = f x $ foldr1 f xs

and

foldl1 f [x] = x
foldl1 f (x:y:ys)=foldl1 f $ f x y : ys

Seen from these, foldl1 seems to use less memory than foldr1 because foldr1 needs to keep an expression like f x1 $ f x2 $ f x3 $ f x4 $... while foldl1 can just calculate f x y everytime and store it as a head element of a list in stead of holding it until it gets to 10^8.

Could anyone tell me what is wrong with my argument?

Answer 1

The right fold can start producing immediately if the combining function is lazy in its second argument. A simplistic example:

foldr1 (++) ["one", "two", "three", ...]
    ~> "one" ++ foldr1 (++) ["two", "three", ...]

and the first part of the result is immediately accessible without further evaluating the second argument of (++). That needs only be evaluated when the first part is consumed. Often, the first part can then already be garbage-collected.

In the example with f = flip const as the combining function, we have a different situation, that is strict⁽¹⁾ in its second argument, but doesn't need to evaluate it at all. And it ignores its first. That is also good for right folds. Here it goes

foldr1 f [x1, x2, x3, ... ]
    ~> f x1 (foldr1 f [x2, x3, ... ])

and now the outermost f can immediately evaluated

    ~> foldr1 f [x2, x3, ... ]
    ~> f x2 (foldr1 f [x3, ... ])
    ~> foldr1 f [x3, ... ]

and at each step, the outermost f can always be immediately evaluated (completely), and one list element thrown away.

If the list is given by a generator that can create it in constant space when sequentially consumed,

last = foldr1 (flip const)

can run in constant space.

With the left fold, things are different. Since that is tail-recursive

foldl1 f (x:y:zs) = foldl f x (y:zs) = foldl f (f x y) zs

it cannot return anything before the fold has reached the end of the list. In particular, a left fold can never terminate on an infinite list.

Now, looking at our case f = flip const, we find

foldl1 f [x1, x2, x3, x4, ...]
    ~> foldl f x1 [x2, x3, x4, ... ]
    ~> foldl f (f x1 x2) [x3, x4, ... ]
    ~> foldl f (f (f x1 x2) x3) [x4, ... ]

Of course it would be possible to immediately evaluate f x1 x2 to x2, and then f x2 x3 = x3, but that is only possible for this special f.

Since foldl is a general higher order function, it cannot evaluate the intermediate results before they are needed, since it is possible that the intermediate results never are needed - and in fact, they are never needed here, at the end of the list, one gets an expression

f (f (f (f ...y3) y2) y1) y0
   ~> y0

and then the outermost f can be evaluated without looking at the huge thunk of nested fs that builds the first argument.

foldl (resp. foldl1) cannot know that it would have been far more efficient to evaluate the intermediate results immediately.

The strict left folds, foldl' and foldl1' do that, they evaluate the intermediate results to weak head normal form (to the outermost value constructor or lambda), and

last = foldl1' (flip const)

would also be very efficient.

But, since the intermediate results are evaluated further than with foldr, they would be a little less efficient, and, importantly, if any list element is ⊥, the foldl1' version would return ⊥:

foldl1' f [x1, ⊥, x3, x4]
    ~> foldl' f x1 [⊥, x3, x4]
    ~> case f x1 ⊥ of
          pattern    -- that causes ⊥
   ~> ⊥

whereas the foldr1 version has no problem with that, since it doesn't inspect the list elements or intermediate results at all.

---

⁽¹⁾ That f is strict in its second argument means that

f x ⊥ = ⊥

Since f simply returns its second argument, that is evidently the case.