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

[Louis Wasserman]

http://hackage.haskell.org/trac/ghc/ticket/3999

Discussion deadline: May 7

Previously, Data.Map's Foldable instance consisted of

instance Foldable (Map k) where
foldMap ...

Even though there were implementations for foldrWithKey and foldlWithKey,
these weren't being used in the Foldable instance -- instead, the slower
version derived from foldMap was in use. This is silly, since foldr and
foldl can be easily derived from foldrWithKey and foldlWithKey.

Additionally, it takes relatively little effort to ensure that keys, elems,
toList, etc. deforest under folds. Therefore, we add the following rewrite
rules:

{-# RULES

"foldr/Data.Map.elems" forall f z m . foldr f z (elems m) = foldr f z m;
"foldl/Data.Map.elems" forall f z m . foldl f z (elems m) = foldl f z m;
"foldr/Data.Map.keys" forall f z m . foldr f z (keys m) = foldrWithKey (\ k
_ -> f k) z m;
"foldl/Data.Map.keys" forall f z m . foldl f z (keys m) = foldlWithKey (\ z
k _ -> f z k) z m;
"foldr/Data.Map.toAscList" forall f z m . foldr f z (toAscList m) =
foldrWithKey (curry f) z m;
"foldl/Data.Map.toAscList" forall f z m . foldl f z (toAscList m) =
foldlWithKey (curry . f) z m; #-}

Finally, we implement foldrWithKey and foldlWithKey for Data.IntMap, and
make the same adjustments to Data.IntMap as to Data.Map, adding specialized
foldr and foldl definitions in the Foldable instance and adding the
corresponding rewrite rules.

The only API change is the addition of foldrWithKey and foldlWithKey to
Data.IntMap, but folds over Maps and IntMaps are exposed to optimization.
Louis Wasserman
wasserman.louis at gmail.com
http://profiles.google.com/wasserman.louis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100421/f2c5a1b7/attachment.html