Map folds in containers: why no worker/wrapper split?

[Milan Straka]

> claus.reinke:
> > Looking at the source code for containers (0.3.0.0),
> > especially the foldWithKey functions in Data.Map and
> > Data.IntMap, I see recursive definitions with non-strict accumulators, 
> > without the usual worker/wrapper
> > split, such as:
> >
> > foldlWithKey :: (b -> k -> a -> b) -> b -> Map k a -> b
> > foldlWithKey _ z Tip              = z
> > foldlWithKey f z (Bin _ kx x l r) =
> >    foldlWithKey f (f (foldlWithKey f z l) kx x) r
> >
> > For comparison, here is base:GHC.List.lhs's definition of foldl:
> >
> > -- We write foldl as a non-recursive thing, so that it
> > -- can be inlined, and then (often) strictness-analysed,
> > -- and hence the classic space leak on foldl (+) 0 xs
> >
> > foldl        :: (a -> b -> a) -> a -> [b] -> a
> > foldl f z0 xs0 = lgo z0 xs0
> >             where
> >                lgo z []     =  z
> >                lgo z (x:xs) = lgo (f z x) xs
> >
> > Doesn't that mean that strictness in the folded
> > Map/IntMap operations cannot be used by the strictness analyser? What am 
> > I missing?
> >
> 
> I bet that's the case.
> 
> Data.Map is the way it is for historical reasons.  It needs a dedicated
> performance maintainer to do detailed benchmarking and static analysis.

I did quite a lot of benchmarking, strictness analysis and performance
improvements to the containers package recently, see the draft of my
paper http://fox.ucw.cz/papers/containers/containers.pdf.

Next week I will start finalizing the patches and submit them. The 'not
generating a worker/wrapper' issue is one of several on my radar, so
this should be resolved.

Cheers,
Milan