Proposal: more general unionWith for Data.Map - Summary

Christian Sattler sattler.christian at
Fri Mar 2 20:16:05 CET 2012

The discussion has been over for a month now, so I think it is prudent 
to summarize the contributions.

There have been many suggestions of a general merge function, but the 
only proposal that matches the expected runtime complexities of the 
specializations to union/intersection/difference/symmetricDifference 
came from Jan-Willem Maessen, who suggested a general merge function of 
the following type:

mergeWithKey :: (Ord k) => (k -> a -> b -> Maybe c) -> (Map k a -> Map k 
c) -> (Map k b -> Map k c) -> Map k a -> Map k b -> Map k c

Existing union/intersection/difference and the missing 
symmetricDifference can be implemented as specialization of this 
function with no loss to runtime complexity when inlining is used, and 
even symmetrizing the behaviour of union.

Feedback indicated it is worth to unify the existing mess with an 
abstract foundation, with otherwise no negative reactions. As such, I 
propose to go through with this.


More information about the Libraries mailing list