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