Improved folds for Data.Map and Data.IntMap
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.
Trac metadata
Trac field | Value |
---|---|
Version | 6.12.1 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | libraries (other) |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |