Proposal: more general unionWith for Data.Map

[Milan Straka]

Hi,

> > On Tue, Jan 24, 2012 at 11:42 AM, Christian Sattler
> > <sattler.christian at gmail.com> wrote:
> > > I don't care much about the naming, but note that the analogous
> > > property already fails for the generalized intersectionWithKey in the
> > > development version.
> > 
> > I suspected as much. I think the current intersectionWithKey is
> > broken. We should have a single function, mergeWithKey, that allows
> > people to do the things they currently do using Maybe return values in
> > e.g. intersectionWithKey.
> 
> Funnily, I just also used mergeWithKey for the "ultimate combining
> function" in this thread :)
> 
> FYI, the new intersectionWithKey is not released yet -- maybe we could
> leave intersectionWithKey as it is, and provide mergeWith[Key] instead.
> Opinions?

Oh, Christian just noted that the performance of
  mergeWithKey :: Ord k => (k -> Maybe a -> Maybe b -> Maybe c) -> Map k a -> Map k b -> Map k c
is too big -- it is at least O(size_of_first_op + size_of_second_op).
But intersectionWithKey and unionWithKey is at most O(size_of_smaller * log(size_of_bigger)).

So the proposal stands: should we add
  mergeWithKey :: Ord k => (k -> a -> a -> Maybe a) -> Map k a -> Map k a -> Map k a
?

Cheers,
Milan