CODEWITHSUNDEEP
haskellfold
tail-event
tail-event

Reputation: 85

Foldl vs Foldr memory usage

Given the Fibonacci infinite list

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

And given the two following calls:

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?

Upvotes: 3

Views: 415

Answers (1)

chi
chi

Reputation: 116139

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.

Upvotes: 6

Related Questions