Proposal: more general unionWith for Data.Map

[Christian Sattler]

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 <john at repetae.net 
> <mailto: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

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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20120126/3cab179e/attachment.htm>