I think I got it. Let's look at the source for Data.Map.map
.
map :: (a -> b) -> Map k a -> Map k b
map f m
= mapWithKey (\_ x -> f x) m
mapWithKey :: (k -> a -> b) -> Map k a -> Map k b
mapWithKey _ Tip = Tip
mapWithKey f (Bin sx kx x l r)
= Bin sx kx (f kx x) (mapWithKey f l) (mapWithKey f r)
Now, mapWithKey
seems to build just the top constructor of the tree and lazily recursing for the two branches... but:
data Map k a = Tip
| Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
Above we see that the subtrees are strict fields! So the recursive calls to mapWithKey
will be forced, causing the full tree to be updated strictly instead of lazily.