Menu
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
900
Only foldr is lazy and can be used for codata/infinite streams. While foldl is tail-recursive (enhanced with strict application foldl' can avoid stack overflow). This is why foldr should be used by default in Haskellin order preserve laziness across function composition.
Difference Between foldl and foldr The difference is that foldl is tail-recursive, whereas foldr is not. With foldr and non-optimized patterns, proc is applied to the current value and the result of recursing on the rest of the list. That is, evaluation cannot complete until the entire list has been traversed.
The added strictness of foldl' doesn't change the way the intermediate list is created. The head of the list remains unavailable until foldl' has finished, so the result will still be slower than with foldr .
From HaskellWiki. The foldr function applies a function against an accumulator and each value of a Foldable structure from right to left, folding it to a single value. foldr is a method of the Foldable typeclass: foldr (++) [] [[0, 1], [2, 3], [4, 5]] -- returns [0, 1, 2, 3, 4, 5]
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.
151
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
