Proposal #3999: Improved folds for Data.Map and Data.IntMap

[Roman Leshchinskiy]

On 24/04/2010, at 00:44, Tyson Whitehead wrote:

> On April 22, 2010 21:11:55 Roman Leshchinskiy wrote:
>> That doesn't really help me, though, because I can't tell why using foldl
>> as opposed to foldl' is essential (or even correct) in these cases. In
>> fact, at a cursory glance a lot of them look quite leaky to me.
> 
> Here's a toy example where replacing foldl with foldl' would be wrong
> 
> sumWhile g y x | g x       = y + x
>               | otherwise = 0
> 
> foldl (sumWhile (< 3)) 6 [5,undefined,4,3,2,1,0]

Just replacing foldl by foldl' isn't always correct, of course. I'd just like to see real-world code where using foldl is both correct (with respect to performance) and essential.

Incidentally, your example aborts with a stack overflow for a list of 5M elements but this function works fine:

  sum . takeWhile (<3) . reverse

The other example, given by Heinrich, was reverse. The report specifies it in terms of foldl but GHC implements it differently.

Roman