Proposal: more general unionWith for Data.Map
Jan-Willem Maessen
jmaessen at alum.mit.edu
Thu Jan 26 00:26:17 CET 2012
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>
More information about the Libraries
mailing list