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@gmail.com http://profiles.google.com/wasserman.louis