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

[Gwern Branwen]

On Thu, Apr 22, 2010 at 4:08 AM, Roman Leshchinskiy <rl at cse.unsw.edu.au> wrote:
>
> 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'.

Not nearly: http://www.reddit.com/r/haskell/comments/bmd5u/thunks_and_haskell/c0nl7u2

There are a lot of foldl uses out there.

-- 
gwern