Christian Sattler | 2 Mar 20:16 2012
Picon

Proposal: more general unionWith for Data.Map - Summary

The discussion has been over for a month now, so I think it is prudent 
to summarize the contributions.

There have been many suggestions of a general merge function, but the 
only proposal that matches the expected runtime complexities of the 
specializations to union/intersection/difference/symmetricDifference 
came from Jan-Willem Maessen, who suggested a general merge function of 
the following type:

mergeWithKey :: (Ord k) => (k -> a -> b -> Maybe c) -> (Map k a -> Map k 
c) -> (Map k b -> Map k c) -> Map k a -> Map k b -> Map k c

Existing union/intersection/difference and the missing 
symmetricDifference can be implemented as specialization of this 
function with no loss to runtime complexity when inlining is used, and 
even symmetrizing the behaviour of union.

Feedback indicated it is worth to unify the existing mess with an 
abstract foundation, with otherwise no negative reactions. As such, I 
propose to go through with this.

Christian
Johan Tibell | 2 Mar 20:23 2012
Picon

Re: Proposal: more general unionWith for Data.Map - Summary

On Fri, Mar 2, 2012 at 11:16 AM, Christian Sattler <sattler.christian <at> gmail.com> wrote:

Feedback indicated it is worth to unify the existing mess with an abstract foundation, with otherwise no negative reactions. As such, I propose to go through with this.

My memory is a bit hazy here, but I thought Milan was working on merging this in. Milan?

-- Johan
 
_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Milan Straka | 3 Mar 10:07 2012
Picon

Re: Proposal: more general unionWith for Data.Map - Summary

Hi all,

> > Feedback indicated it is worth to unify the existing mess with an abstract
> > foundation, with otherwise no negative reactions. As such, I propose to go
> > through with this.
> 
> 
> My memory is a bit hazy here, but I thought Milan was working on merging
> this in. Milan?

Yes, I am working on merging mergeWith and mergeWithKey with the type
you specified, in Map and IntMap.

Hopefully, IntMap.{union*, difference*, intersecion*} and
Map.intersection* will be implemented using mergeWith*, depending what
the benchmarks reveal. I am not sure about Map.{union*, difference*}, as
they use different algorithm -- I am waiting for the benchmarks.

Cheers,
Milan

Gmane