Re: Proposal: more general unionWith for Data.Map

On 01/25/2012 11:26 PM, Jan-Willem Maessen wrote:

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 mailto: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

I don't think this solves the complexity issue e.g. for symmetric difference of a large set of size n^2 with a small set of size n.