23

Haskell has two left fold functions for lists: foldl, and a "strict" version, foldl'. The problem with the non-strict foldl is that it builds a tower of thunks:

    foldl (+) 0 [1..5]
--> ((((0 + 1) + 2) + 3) + 4) + 5
--> 15

This wastes memory, and may cause a stack overflow if the list has too many items. foldl', on the other hand, forces the accumulator on every item.

However, as far as I can tell, foldl' is semantically equivalent to foldl. Evaluating foldl (+) 0 [1..5] to head normal form requires forcing the accumulator at some point. If we didn't need a head-normal form, we wouldn't be evaluating foldl (+) 0 [1..5] to begin with.

Is there any compelling reason one would want the behavior of foldl over that of foldl' ?

Joey Adams
  • 41,996
  • 18
  • 86
  • 115

2 Answers2

27

foldl and foldl' are not semantically equivalent. Trivial counterexample:

Prelude Data.List> foldl (\x y -> y) 0 [undefined, 1]
1
Prelude Data.List> foldl' (\x y -> y) 0 [undefined, 1]
*** Exception: Prelude.undefined

In practice, however, you usually want the strict foldl' for the reasons you mentioned.

hammar
  • 138,522
  • 17
  • 304
  • 385
14

When foldl and foldl' wouldn't produce the same result, as in hammar's example, the decision has to be made according to the desired outcome. Apart from that, you'd use foldl rather than foldl' if the folded function is a constructor (applying a constructor creates a value in WHNF, there's no point in forcing it to WHNF again), and in foldl (.) id functions where forcing WHNF doesn't gain anything either. Apart from these exceptional cases, foldl' is the method of choice.

Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
  • 1
    I don't believe there would ever be a reason to use `foldl (.) id functions` over `foldr (.) id functions`. They are semantically equivalent, when the former is not `_|_`, so only the latter allows lazy consumption of the functions. Am I mistaken? – luqui Nov 23 '11 at 01:18
  • 1
    @luqui: I think it's just the opposite. The foldr version looks like: `(\x acc -> x . acc)`, which will essentially mean: perform the *rightmost* function first, thus disallowing lazy consumption. Am I mistaken? :) – Dan Burton Nov 23 '11 at 01:22
  • @DanBurton If the functions can start producing output without knowing their argument, `foldr` allows lazy consumption (consider `foldr (.) id [(string++) | string <- strings]`. @luqui Now you mention it, I don't know a reason to `foldl` (.) id functions` either. – Daniel Fischer Nov 23 '11 at 01:49
  • 8
    @DanBurton, the order of information flow is potentially opposite that in a call by value language. `f (g x)` only performs `g` "first" in your mind. In fact it is `f` that has the first chance to produce information. Consider `f x = 1:x`; `g x = g x`. – luqui Nov 23 '11 at 01:54
  • @luqui: ah yes, that makes sense. Playing with this idea has led me to ask [a new question](http://stackoverflow.com/questions/8249958/folding-function-composition-monads-and-laziness-oh-my). – Dan Burton Nov 23 '11 at 22:29