Argh, sent this out before in reply to the wrong message (and not reply-to-all).  Sorry Milan.

On Tue, Jan 24, 2012 at 6:08 PM, John Meacham <john@repetae.net> wrote:

I have needed this before

merge :: (a -> b -> Maybe c) -> (a -> Maybe c) -> (b -> Maybe c) ->

Map k a -> Map k b -> Map k c

mergeWithKey :: (k -> a -> b -> Maybe c) -> (k -> a -> Maybe c) ->
(k-> b -> Maybe c) -> Map k a -> Map k b -> Map k c

where the function arguments are
what to use when the key appears in both maps
what to use when the key appears in just the left map
what to use when the key appears in just the right map.

It seems like it would be the ultimate fully general fast map merging routine.

intersection = merge (Just . const) (const Nothing) (const Nothing)
union = merge (Just . const) Just Just
xor = merge ( const Nothing . const) Just Just

and so forth...

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