Foldl vs Foldr memory usage

Question

Given the Fibonacci infinite list

fibo a b = a : fibo b (a+b)

And given the two following calls:

• foldl (+) 1 (take 1000000 $ fibo 1 1)
• foldr (+) 1 (take 1000000 $ fibo 1 1)

I expected the first one (foldl) to allocate a huge amount of memory because of thunks and in fact that's what happens.

However, I didn't expect the same for the second one. Because of how the foldr is defined I thought a usual stack like evaluation would have been performed for the right argument of (+) (because of its strictness).

Actually even in this case I have a huge amount of memory that is allocated.

What is happening?

Answer 1

foldr f z xs is inefficient when f is strict on its second argument (like (+)), since it evaluates to

f1 x1 (f x2 (f x3 ...

and this can not start to evaluate until the very end of the list. If f were not strict on the second argument, evaluation could instead start sooner.