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. Christian