Haskell thunks - foldl vs foldr

Question

Learning Haskell, I came across the fact that foldl creates thunks and might crash the stack, so it's better to use foldl' from Data.List. Why is it just foldl, and not, for example, foldr?

Thanks

Answer 1

There is no need for foldr' because you can cause the effect yourself.

Here is why: Consider foldl f 0 [1,2,3]. This expands to f (f (f 0 1) 2) 3, so by the time you get anything back to work with, thunks for (f 0 1) and (f (f 0 1) 2) have to be created. If you want to avoid this (by evaluating these subexpressions before continuing), you have to instruct foldl to do it for you – that is foldl'.

With foldr, things are different. What you get back from foldr f 0 [1, 2, 3] is f 1 (foldr f 0 [2, 3]) (where the expression in parenthesis is a thunk). If you want to evaluate (parts of) the outer application of f, you can do that now, without a linear number of thunks being created first.

But in general, you are using foldr with lazy functions for f that can already do something (e.g. produce list constructors) before looking at the second argument.

Using foldr with a strict f (e.g. (+)) has the unwanted effect of putting all applications on the stack until the end of the list is reached; clearly not what you want, and not a situation where a however-looking foldr' could help.