mapEither is inefficient

[treeowl]

It first builds lists, then converts them lazily into multisets. I think it makes a lot more sense to accumulate those multisets eagerly.

[twanvl]

That seems sensible, something like

mapEither :: (Ord b, Ord c) => (a -> Either b c) -> MultiSet a -> (MultiSet b, MultiSet c)
mapEither f = go empty empty . Map.toList . unMS
  where mapEither' ls rs [] = (ls, rs)
        mapEither' ls rs ((x,n):xs) = case f x of
           Left  l -> let ls' = insertMany l n ls in ls' `seq` mapEither' ls' rs xs
           Right r -> let rs' = insertMany r n rs in rs' `seq` mapEither' ls rs' xs