Re: Proposal: more general unionWith for Data.Map

On 01/26/2012 12:08 AM, Jan-Willem Maessen wrote:

On Wed, Jan 25, 2012 at 7:01 PM, Christian Sattler mailto:sattler.christian@gmail.com> wrote:

...

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

Er, could you be more specific? What case is not handled that prevents us from matching the asymptotic complexity of a hand-written symmetric difference function? There should be O(n) tree splits and joins in either case.

-Jan

Ah, yes, you are right. Mistake on my part. +1 for the proposal