Map folds in containers: why no worker/wrapper split?
Claus Reinke
claus.reinke at talk21.com
Thu Jun 17 15:52:45 EDT 2010
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?
Claus
More information about the Libraries
mailing list