#3999: Improved folds for Data.Map
---------------------------------+------------------------------------------
Reporter: LouisWasserman | Owner:
Type: proposal | Status: new
Priority: normal | Component: libraries (other)
Version: 6.12.1 | Keywords:
Os: Unknown/Multiple | Testcase:
Architecture: Unknown/Multiple | Failure: None/Unknown
Patch: 1 |
---------------------------------+------------------------------------------
This proposal aims to make the following improvements:
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.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/3999>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
