Proposal: more general unionWith for Data.Map
Christian Sattler
sattler.christian at gmail.com
Thu Jan 26 01:12:40 CET 2012
On 01/26/2012 12:08 AM, Jan-Willem Maessen wrote:
>
>
> On Wed, Jan 25, 2012 at 7:01 PM, Christian Sattler
> <sattler.christian at gmail.com <mailto: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
Ah, yes, you are right. Mistake on my part. +1 for the proposal
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20120126/52d3da62/attachment-0001.htm>
More information about the Libraries
mailing list