Hi,
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.
FYI, development version of containers has generalized intersectionWith[Key] with type intersectionWithKey :: Ord k => (k -> a -> b -> Maybe c) -> Map k a -> Map k b -> Map k c If others agree, it is indeed simple to generalize type of unionWith[Key] from unionWithKey :: Ord k => (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a to unionWithKey :: Ord k => (k -> a -> a -> Maybe a) -> Map k a -> Map k a -> Map k a These functions are used quite frequently in my opinion, so it will probably result in quite a lot of code breaks (unionWith (++) has to be changed to unionWith (\a b -> Just (a ++ b))). Any opinion, noble almighty others? Cheers, Milan