Is foldl ever preferable to its strict cousin, fol

问题:

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

回答1:

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.

回答2:

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.