Proposal: more general unionWith for Data.Map

[Christian Sattler]

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>