Implications of foldr vs. foldl (or foldl’)

by

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.

More Related Contents:

  1. Writing foldl using foldr
  2. What are paramorphisms?
  3. What constitutes a fold for types other than list?
  4. Using Haskell’s map function to calculate the sum of a list
  5. Implement zip using foldr
  6. Way to go from recursion to iteration
  7. What is a monad?
  8. Solution for “Fatal error: Maximum function nesting level of ‘100’ reached, aborting!” in PHP
  9. Determining complexity for recursive functions (Big O notation)
  10. Tower of Hanoi: Recursive Algorithm
  11. recursive variadic template to print out the contents of a parameter pack
  12. How do you represent a graph in Haskell?
  13. How do functors work in haskell?
  14. Recursion vs loops
  15. Is Haskell truly pure (is any language that deals with input and output outside the system)?
  16. How to compose `not` with a function of arbitrary arity?
  17. Functional programming, Scala map and fold left [closed]
  18. Why is lazy evaluation useful?
  19. Uses for Haskell id function
  20. Pattern matching identical values
  21. What is a monad?
  22. How to increment a variable in functional programming?
  23. Examples of Recursive functions [closed]
  24. Why are side-effects modeled as monads in Haskell?
  25. Abusing the algebra of algebraic data types – why does this work?
  26. How to interpret bind/>>= of the function instance?
  27. Python recursive function to display all subsets of given set
  28. Functional lenses
  29. Why does OCaml sometimes require eta expansion?
  30. Explanation of “tying the knot”

Leave a Comment