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

[Roman Leshchinskiy]

On 22/04/2010, at 13:18, Louis Wasserman wrote:

> > {-# 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; #-}
> A few thoughts on this issue:
> 	• I've occasionally had problems getting inlining to actually happen, which is irritating.
> 	• Maintaining portability requires almost as much code for the preprocessor as the rules I wrote above, and is finicky at best.
> 	• Perhaps my biggest concern with that approach is that it doesn't play nicely with foldl, which came up in the application that motivated this proposal!  The rewrite rule approach I outline above is perfectly compatible with foldr/build rewriting, but also permits foldls to function nicely.

Ah, I missed the foldl rules. Alas, I don't think they'll work reliably. You'd have to delay inlining foldl to give them a chance to fire but that requires a change to base. BTW, you also have to make sure that elems, keys etc. don't get inlined prematurely with appropriate INLINE/NOINLINE pragmas.

The rules don't work well with GHC's list fusion system, either. To see why, look for rules involving build in GHC.List (esp. foldr2) and for augment in GHC.Base.

FWIW, I'm a bit surprised that you need foldl on lists anyway. I thought everybody uses foldl'.

Roman