Proposal: more general unionWith for Data.Map

[Jan-Willem Maessen]

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 at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20120125/f9d81ea6/attachment.htm>