Foldl vs Foldr memory usage

3
votes

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?

1
haskellfold
The best function for doing that particular task efficiently is foldl'. It's possible to do it efficiently using foldr, but only in a somewhat twisted fashion: foldr (\x r acc -> r $! x + acc) id (take ...) 1. - dfeuer

1 Answers

6
votes

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.