Names for general merge tactics in Data.Map

[David Feuer]

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