Proposal #3999: Improved folds for Data.Map and Data.IntMap
Roman Leshchinskiy
rl at cse.unsw.edu.au
Wed Apr 21 21:27:07 EDT 2010
On 22/04/2010, at 08:47, Louis Wasserman wrote:
> 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; #-}
Why not implement elems etc. in terms of build? This would make them play nicely with foldr/build fusion at no cost.
Roman
More information about the Libraries
mailing list