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