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

[Don Stewart]

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.

-- Don