Proposal: strictify foldl'

[David Feuer]

As Duncan Coutts explains toward the end of
http://www.well-typed.com/blog/90/ (which proposes something else I
personally *don't* endorse), foldl', the strict foldl, isn't actually
strict enough. In particular, it's only conditionally strict in the initial
value for the accumulator:

foldl' (\_ x -> x) undefined [3] = 3


Why does this matter? Strictness analysis needs to look at (and be able to
look at) the function passed to foldl' to determine whether the expression
is strict in the initial value. foldl'-as-foldr tends to complicate this
sort of analysis already.

Proposal: make foldl' unconditionally strict in the initial accumulator
value, both in GHC.List and in (the default definition in) Data.Foldable,
and make foldr' in Data.Foldable unconditionally strict in the initial
value of its accumulator.

Specifically,

foldl' k z0 xs =
  foldr (\v fn z -> z `seq` fn (k z v)) id xs z0

would change to

foldl' k !z0 xs =
  foldr (\v fn z -> z `seq` fn (k z v)) id xs z0
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20141103/ff822687/attachment.html>