Proposal: more general unionWith for Data.Map

[Jan-Willem Maessen]

On Wed, Jan 25, 2012 at 7:01 PM, Christian Sattler <
sattler.christian at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20120125/d847c86c/attachment.htm>