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