Names for general merge tactics in Data.Map

[David Feuer]

I like the idea of using separate modules. What would you like them to
be called?

I am open to the idea of leaving mergeWithKey in, but I'm not yet
convinced. Can you give an example of a realistic application of
mergeWithKey that cannot easily be rewritten in terms of generalMerge?
I would normally agree with you that backwards compatibility should be
preserved. However, mergeWithKey has several very serious problems.

1. It allows the user to produce invalid maps. Unlike other functions
that do so, it's not clear that it offers any significant efficiency
benefit (once generalMerge is added).

2. It breaks the map abstraction. A user could invoke mergeWithKey
with arguments that cause it to produce semantically different maps
depending on the way the given map is balanced. For example, a user
could pass an only1 function that deletes the median of the tree it is
passed. I don't know how to document the appropriate restrictions
required to preserve the abstraction.

3. It is very hard to figure out much about what mergeWithKey does by
looking at its name and type. Indeed, I did not understand it from its
documentation either, and had to read the source code.

On Thu, Aug 18, 2016 at 4:19 PM, Eric Mertens <emertens at gmail.com> wrote:
> My initial reaction to this is that I'd like to see mergeWithKey left alone,
> there is existing code using it and it continues to be useful, and then to
> have this new API offered in its own module under Data.Map where the various
> consumers and providers of WhenMatched and WhenMissing can live and be
> documented as a coherent toolkit.
>
> On Thu, Aug 18, 2016 at 1:08 PM David Feuer <david.feuer at gmail.com> wrote:
>>
>> As I described previously, I've come up with general merge functions
>> for Data.Map to replace the problematic mergeWithKey (which I desire
>> to deprecate and remove). I have provisional names for the functions,
>> and also for the "merge tactics" that go with them and their types. I
>> would like to get whatever feedback I can before actually adding
>> these. I'd like to try to make a release including these functions
>> within approximately two weeks, so prompt responses will be
>> appreciated.
>>
>> Note that the names of the "merge tactics" break with the tradition of
>> offering plain functions and WithKey versions. To cut down on the
>> already-large API, only key-passing versions will be provided (unless
>> people object strongly). This has a small potential efficiency cost,
>> but it cuts the API in half.
>>
>>
>> The most general function is
>>
>> generalMergeA :: (Applicative f, Ord k) => WhenMissing f k a c ->
>> WhenMissing f k b c -> WhenMatched f k a b c -> Map k a -> Map k b ->
>> f (Map k c)
>>
>> and the pure version is
>>
>> generalMerge :: Ord k => SimpleWhenMissing k a c -> SimpleWhenMissing
>> k b c -> SimpleWhenMatched k a b c -> Map k a -> Map k b -> Map k c
>>
>> where
>> type SimpleWhenMissing = WhenMissing Identity
>> type SimpleWhenMatched = WhenMatched Identity
>>
>> WhenMissing and WhenMatched are "merge tactics" explaining what to do
>> with elements in various situations. WhenMissing explains what to do
>> with keys present in one map but not the other, while WhenMatched
>> explains what to do with keys present in both maps:
>>
>> WhenMissing f k x z is an abstract representation of a function of
>> type k -> x -> f (Maybe z)
>>
>> WhenMatched f k x y z is an abstract representation of a function of
>> type k -> x -> y -> f (Maybe z)
>>
>> So in principle, we have
>>
>> generalMergeA ~::~
>>   (Applicative f, Ord k)
>>   => (k -> a -> f (Maybe c))
>>   -> (k -> b -> f (Maybe c))
>>   -> (k -> a -> b -> f (Maybe c))
>>   -> Map k a -> Map k b -> f (Map k c)
>>
>> By using these abstract merge tactics instead of functions, we gain
>> the ability to perform various optimizations. At present, only the
>> WhenMissing optimizations are performed (they seem to be the most
>> important), but we may choose to add WhenMatched optimizations in the
>> future to enhance sharing.
>>
>> There are various ways to construct the merge tactics. The most
>> general are currently called
>>
>> traverseMaybeMissing :: Applicative f => (k -> x -> f (Maybe y)) ->
>> WhenMissing f k x y
>>
>> and
>>
>> zipWithMaybeAMatched :: Applicative f => (k -> x -> y -> f (Maybe z))
>> -> WhenMatched f k x y z
>>
>> These directly convert functions into merge tactics with the
>> corresponding types. There are various others that are simpler and/or
>> faster. Generally, the pure tactics have the advantage of being able
>> to process a whole subtree in a single Applicative action. Non-Maybe
>> tactics have the advantage of skipping balance checks. dropMissing and
>> preserveMissing are especially important because they can skip over
>> whole subtrees, either pruning them or leaving them alone.
>>
>> Pure:
>>
>> dropMissing :: Applicative f => WhenMissing f k x y
>> -- dropMissing :: SimpleWhenMissing k x y
>>
>> preserveMissing :: Applicative f => WhenMissing f k x x
>> -- preserveMissing :: SimpleWhenMissing k x x
>>
>> mapMaybeMissing :: Applicative f => (k -> x -> Maybe y) -> WhenMissing f k
>> x y
>> -- mapMaybeMissing :: (k -> x -> Maybe y) -> SimpleWhenMissing k x y
>>
>> mapMissing :: Applicative f => (k -> x -> y) -> WhenMissing f k x y
>> -- mapMissing :: (k -> x -> y) -> SimpleWhenMissing k x y
>>
>> filterMissing :: Applicative f => (k -> x -> Bool) -> WhenMissing f k x x
>> -- filterMissing :: (k -> x -> Bool) -> SimpleWhenMissing k x x
>>
>>
>> zipWithMaybeMatched :: Applicative f => (k -> x -> y -> Maybe z) ->
>> WhenMatched f k x y z
>> -- zipWithMaybeMatched :: (k -> x -> y -> Maybe z) -> SimpleWhenMatched k
>> x y z
>>
>> zipWithMatched :: Applicative f => (k -> x -> y -> z) -> WhenMatched f k x
>> y z
>> -- zipWithMatched :: (k -> x -> y -> z) -> SimpleWhenMatched k x y z
>>
>> Applicative:
>>
>> traverseMissing :: Applicative f => (k -> x -> f y) -> WhenMissing f k x y
>>
>> filterAMissing :: Applicative f => (k -> x -> f Bool) -> WhenMissing f k x
>> x
>>
>> zipWithAMatched :: Applicative f => (k -> x -> y -> f z) ->
>> WhenMatched f k x y z
>>
>>
>> Thanks,
>> David Feuer
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>