Proposal #3999: Improved folds for Data.Map and Data.IntMap
Heinrich Apfelmus
apfelmus at quantentunnel.de
Sat Apr 24 04:48:05 EDT 2010
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
More information about the Libraries
mailing list