Re: Proposal: strictify foldl'

Hi all, FYI, foldl's in containers already have this property being strict in the initial value. Therefore, Data.Map.foldl' (\_ x -> x) undefined $ Data.Map.fromList [(4,2)] triggers *** Exception: Prelude.undefined Nevertheless, silent change in Data.List.foldl' semantics sounds kinda dangerous. Cheers, Milan

-----Original message----- From: David Feuer Sent: 3 Nov 2014, 11:51

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

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries