Implications of foldr vs. foldl (or foldl')

Question

Firstly, Real World Haskell, which I am reading, says to never use foldl instead of foldl'. So I trust it.

But I'm hazy on when to use foldr vs. foldl'. Though I can see the structure of how they work differently laid out in front of me, I'm too stupid to understand when "which is better." I guess it seems to me like it shouldn't really matter which is used, as they both produce the same answer (don't they?). In fact, my previous experience with this construct is from Ruby's inject and Clojure's reduce, which don't seem to have "left" and "right" versions. (Side question: which version do they use?)

Any insight that can help a smarts-challenged sort like me would be much appreciated!

Answer 1

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-commuative operations, such as subtraction.

Haskell.org has an interesting article on the subject.

Answer 2

Shortly, foldr is better when the accumulator function is lazy on its second argument. Read more at http://www.haskell.org/haskellwiki/Stack_overflow (pun intended).

Answer 3

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 value of f x y can be computed using only on 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 is 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.

Answer 4

Foldr illustrated. Foldl illustrated

Answer 5

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.

Answer 6

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.

Answer 7

As Konrad points out, their semantics are different. They don't even have the same type:

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci>

For example, the list append operator (++) can be implemented with foldr as

(++) = flip (foldr (:))

while

(++) = flip (foldl (:))

will give you a type error.

Answer 8

foldr looks like this:

foldl looks like this:

Context: Fold on the Haskell wiki