I wanted to demonstrate partitionKeys recently (#975 (comment)) and realized that the public Map.Merge API is not expressive enough for it.

What I need:

wm1 :: WhenMissing Pair k a a
wm1 = WhenMissing (\t -> Pair empty t) (\_ x -> Pair Nothing (Just x))

Best I can do with the public API:

wm1 :: WhenMissing Pair k a a
wm1 = traverseMaybeMissing (\_ x -> Pair Nothing (Just x))

which is terribly inefficient! (O(1) vs O(n))

Is there a safe way to allow such use cases?