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

[Heinrich Apfelmus]

Roman Leshchinskiy wrote:
> Heinrich Apfelmus wrote:
>> Roman Leshchinskiy wrote:
>>
>>> Hmm, I'd love to see some real-world uses of foldl. I have no idea
>>> what to optimise it for in vector. Unfortunately, the link above
>>> doesn't give any examples.
>>
>> Here a use of foldl from the Haskell98 Prelude:
>>
>>    reverse :: [a] -> [a]
>>    reverse = foldl (flip (:)) []
>>
>> Basically, foldl is useful if the accumulating parameter uses equal or
>> more space if evaluated to normal form than the input list.
> 
> What would change if this used foldl' instead?

Nothing much, the  flip (:) a x  will be evaluated to  x:a  a bit
earlier. By inlining the  foldl , GHC even skips that tiny evaluation.
Note however that it doesn't `seq` the accumulating parameter as  foldl'
 would do.

In any case, since the accumulating parameter has the same size in both
unevaluated form and in normal form, the choice between  foldl  or
foldl' doesn't make much of a difference. I don't know of any real world
examples where this is not the case, but it's not too difficult to come
up with artificial ones, like

    let f a n = let x = replicate n n in x `seq` (x : a)
    in foldl f [] [1..20]

Here, forcing the spine of the list forces the large elements as well.
But this is probably best written along the lines of

    reverse $ map (\n -> replicate n n) [1..20]

anyway.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com