Proposal: more general unionWith for Data.Map

[Bertram Felgenhauer]

Milan Straka wrote:
> Anyway, we could instead of proposed unionWithKey offer functions
>   mergeWith :: Ord k => (Maybe a -> Maybe b -> Maybe c) -> Map k a -> Map k b -> Map k c
>   mergeWithKey :: Ord k => (k -> Maybe a -> Maybe b -> Maybe c) -> Map k a -> Map k b -> Map k c
> The combining function is executed for every unique key from both maps.
> All functions unionWith, intersectionWith, differencseWith, proposed
> unionWith can be expressed using this function.
> 
> But I am not sure about the performance (using so many Maybes).

There's a bigger problem with performance than this constant factor,
namely that it's no longer possible to short-cut evaluation for
subtrees of the map that are known to be disjoint. For example,
empty `intersect` x currently can be computed in constant time,
no matter what x is; this can not be done with `merge`.

This reasoning justifies the existence of intersection, union and
difference functions in Data.Map in addition to a merge function.

Of course, the functions union, intersect and difference could be
implemented as a single function that takes two boolean arguments
to specify which of the disjoint parts to keep in the result.

Bertram