Search code examples
haskellfoldstrictness

Is foldl ever preferable to its strict cousin, foldl'?


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' ?


Solution

  • 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.