...
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