Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implications of foldr vs. foldl (or foldl')

People also ask

Is foldr or foldl more efficient?

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.

What is the difference between foldl and foldr?

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.

Why is foldr lazy?

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:

Right-fold visualization

foldl looks like this:

Left-fold visualization

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 Ints, Doubles, Floats. Integers 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.