Haskell thunks - foldl vs foldr

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

thanks

+4
source share
1 answer

There is no need to foldr' , because you can trigger the effect yourself.

Here's why: Consider foldl f 0 [1,2,3] . This expands to f (f (f 0 1) 2) 3 , so by the time you get something back to work, you need to create tricks for (f 0 1) and (f (f 0 1) 2) . If you want to avoid this (by evaluating these subexpressions before continuing), you must tell foldl to do this for you - it's foldl' .

With foldr things are different. The fact that you will return from foldr f 0 [1, 2, 3] is f 1 (foldr f 0 [2, 3]) (where the expression in brackets is thunk). If you want to evaluate (part) of an external application f , you can do it now, without creating a linear number of thunks created.

But in the general case, you use foldr with lazy functions for f that can already do something (for example, create list constructors) before looking at the second argument.

Using foldr with strict f (for example, (+) ) has the undesirable effect of placing all applications on the stack until the end of the list is reached; clearly not what you want, not a situation in which looking foldr' might help.

+10
source

All Articles