Map folds in containers: why no worker/wrapper split?
Don Stewart
dons at galois.com
Thu Jun 17 15:55:22 EDT 2010
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
More information about the Libraries
mailing list