Haskell Wiki compares foldr , foldl and foldl' and recommends using either foldr or foldl' . foldl' is the more efficient way to arrive at that result because it doesn't build a huge thunk.
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.
On the other hand, consider foldr . It's also lazy, but because it runs forwards, each application of f is added to the inside of the result. So, to compute the result, Haskell constructs a single function application, the second argument of which is the rest of the folded list.
The recursion for foldr f x ys
where ys = [y1,y2,...,yk]
looks like
f y1 (f y2 (... (f yk x) ...))
whereas the recursion for foldl f x ys
looks like
f (... (f (f x y1) y2) ...) yk
An important difference here is that if the result of f x y
can be computed using only the value of x
, then foldr
doesn't' need to examine the entire list. For example
foldr (&&) False (repeat False)
returns False
whereas
foldl (&&) False (repeat False)
never terminates. (Note: repeat False
creates an infinite list where every element is False
.)
On the other hand, foldl'
is tail recursive and strict. If you know that you'll have to traverse the whole list no matter what (e.g., summing the numbers in a list), then foldl'
is more space- (and probably time-) efficient than foldr
.
foldr
looks like this:
foldl
looks like this:
Context: Fold on the Haskell wiki
Their semantics differ so you can't just interchange foldl
and foldr
. The one folds the elements up from the left, the other from the right. That way, the operator gets applied in a different order. This matters for all non-associative operations, such as subtraction.
Haskell.org has an interesting article on the subject.
Shortly, foldr
is better when the accumulator function is lazy on its second argument. Read more at Haskell wiki's Stack Overflow (pun intended).
The reason foldl'
is preferred to foldl
for 99% of all uses is that it can run in constant space for most uses.
Take the function sum = foldl['] (+) 0
. When foldl'
is used, the sum is immediately calculated, so applying sum
to an infinite list will just run forever, and most likely in constant space (if you’re using things like Int
s, Double
s, Float
s. Integer
s will use more than constant space if the number becomes larger than maxBound :: Int
).
With foldl
, a thunk is built up (like a recipe of how to get the answer, which can be evaluated later, rather than storing the answer). These thunks can take up a lot of space, and in this case, it’s much better to evaluate the expression than to store the thunk (leading to a stack overflow… and leading you to… oh never mind)
Hope that helps.
By the way, Ruby's inject
and Clojure's reduce
are foldl
(or foldl1
, depending on which version you use). Usually, when there is only one form in a language, it is a left fold, including Python's reduce
, Perl's List::Util::reduce
, C++'s accumulate
, C#'s Aggregate
, Smalltalk's inject:into:
, PHP's array_reduce
, Mathematica's Fold
, etc. Common Lisp's reduce
defaults to left fold but there's an option for right fold.
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