Add mapPair

[treeowl]

mapEither isn't very general as a multiset operation. It generalizes nicely to

mapPair
  :: Ord a
  => (a -> Occur -> ((b, Occur), (c, Occur)))
  -> MultiSet a -> (MultiSet b, MultiSet c)

By digging into Data.Map internals, it's also possible to write a very efficient version for when the passed function is strictly increasing (relative to the natural partial ordering of pairs).

mapPairAsc
  :: (a -> Occur -> ((b, Occur), (c, Occur)))
  -> MultiSet a -> (MultiSet b, MultiSet c)

[twanvl]

At this point, isn't mapPair just two maps?

mapPair f ms = (mapOccur (\x o -> fst (f x o)) ms, mapOccur (\x o -> snd (f x o)) ms)

Where

mapOccur :: Ord b => (a -> Occur -> (b, Occur)) -> MultiSet a -> MultiSet b

[treeowl]

It's exactly two maps, done in one pass.

[twanvl]

But what is the advantage of doing it in one pass? We don't want to add mapFilterFoldInOnePass :: (Ord a, Ord b, Monoid c) => (a -> (b,Bool,c)) -> MultiSet a -> (MultiSet a, MultiSet b, c) just because multiple things can be done in one pass.

[treeowl]

So why do we have mapEither? I think mapPair makes a lot more sense than that does in a multiset context.

[twanvl]

You can't implement mapEither in terms of other maps, and also not in terms of the proposed mapPair. Additionally, mapEither also exists in Data.Map, and Data.MultiSet tries to mirror that API.

For mapPair I see no advantage over using two maps. Not in terms of efficiency or convenience at least.

[treeowl]

You're right; I've made a mistake. You'd need mapThese to deal with the zeros.