Proposal: more general unionWith for Data.Map
Christian Sattler
sattler.christian at gmail.com
Thu Jan 26 01:01:32 CET 2012
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>
More information about the Libraries
mailing list