Proposal: strictify foldl'

[Milan Straka]

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 <david.feuer at gmail.com>
> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries