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