...
As others (including Milan) observed, this isn't
asymptotically efficient if the maps don't overlap much.
Better is the following swiss
army knife of combining functions:
combine :: Ord k => (k -> a -> b -> Maybe c)
-- Combine common entries
-> (Map k a -> Map k c)
-- Convert left submap with no common entries
-> (Map k b -> Map k c)
-- Convert right submap with no common entries
-> Map k a -> Map k b
-> Map k c
Now
unionWithKey f = combine (\k a b -> Just (f k a b))
id id
intersectionWithKey f = combine f (const empty) (const
empty)
with no change in asymptotic complexity, and a bunch of
fusion laws with fmap hold. This also permits difference
and symmetric difference to be easily defined:
difference = combine (\_ _ _-> Nothing) id (const
empty)
symmDifference = combine (\_ _ _ -> Nothing) id id
When you inline combine and (where necessary) mapWithKey,
you get exactly the code you'd expect without fancy footwork
to delete the identity tree traversals.
-Jan