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

Question

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

Minardi

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

Edaedacious

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

Confirmation

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? – Emory

@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? :) – Godforsaken

@DanBurton If the functions can start producing output without knowing their argument, foldr allows lazy consumption (consider foldr (.) id [(string++) | string <- strings]. @Emory Now you mention it, I don't know a reason to foldl (.) id functions` either. – Confirmation

@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. – Emory

@luqui: ah yes, that makes sense. Playing with this idea has led me to ask a new question. – Godforsaken