Proposal: more general unionWith for Data.Map

[Christian Sattler]

Hi all,

There are some high-level operations on maps which take two tree 
traversals only because the interface fails to expose sufficiently 
general functions. This proposal is concerned with an analogue of 
unionWithKey of type Ord k => (k -> a -> a -> Maybe a) -> Map k a -> Map 
k a -> Map k a, with the intended semantics that if a key is present in 
both maps and the operation applied to the key and corresponding values 
returns Nothing, the key is deleted from the result.

Example use: sparse vectors are represented as maps from indices to 
non-zero coordinates. Often, a highly sparse vector u needs to be a 
added to a rather dense sparse vector v, i.e. we have m << n where m and 
n are the counts of non-zero elements in u and v, respectively. I need 
this operation to be O(m + n) as well as O(m * log(n)), and it should be 
as efficient as reasonable possible. This seems like a straightforward 
use case for unionWith since its hedge-union algorithm guarantees O(m * 
log(n)). The only problem occurs when u[i] = x and v[i] = -x for some 
index i and non-zero x, resulting in a zero entry I would rather have 
deleted from the result (this is a common case when dealing with 
matrices with small integer entries). The same problems occurs for 
coordinate-wise vector multiplication over non-integral domains, this 
time with intersectionWith.

Remarks:
- It would align the types of unionWith and intersectionWith with 
differenceWith.
- The concept of allowing operations with return type Maybe a to avoid 
an additional high-level operation is already expressed in functions 
like alter or mapMaybeWithKey.
- It would enable an efficient implementation of symmetricDifference = 
unionMaybeWithKey (const Nothing).
- This concerns Data.Map, Data.IntMap, Data.Set, Data.IntSet and the 
With[Key] versions of union/intersection/difference
- At least for Data.Map.unionWithKey, modifying the existing 
implementation seems trivial, requiring a merge instead of a join in the 
new case.

I apologize if some of these points have been brought up before.

Christian