MapMonoid.md

The Monoid instance for Data.Map comes with a left-biased Monoid instance:

> Map.fromList [(1,'a')] <> Map.fromList [(1,'b'),(2,'x')]
Map.fromList [(1,'a'),(2,'x')]

While this is a perfectly valid monoid it might not alwasy be the one that you want. Thanks to -XDerivingVia we can now choose our own instance. This newtype behaves like a traditional map, except that it merges colliding elements pointwise.

newtype MonoidMap k a = MonoidMap { getMonoidMap :: Map k a }

instance (Ord k, Semigroup v) =>
  Semigroup (MonoidMap k v) where
    MonoidMap a <> MonoidMap b =
      MonoidMap $ Map.unionWith (<>) a b

instance (Ord k, Semigroup v) =>  Monoid (MonoidMap k v) where
  mempty  = MonoidMap $ Map.empty
  mappend = (<>)

Let's see it in action:

>>> Map.fromList [(1,"a")] <> Map.fromList [(1,"b"),(2,"x")]
Map.fromList [(1,"ab"),(2,"x")]

We can obtain traditional left-bias using:

newtype LeftMap k a = LeftMap { getLeftMap :: Map k (First a) }
  deriving (Semigroup, Monoid)
    via (MonoidMap k (First a))

Or indeed right:

newtype RightMap k a = RightMap { getRightMap :: Map k (Last a) }
  deriving (Semigroup, Monoid)
    via (MonoidMap k (Last a))

It also allows for a concise deginition of multimaps:

newtype MultiMap k a = MultiMap { getMultiMap :: Map k [a] }
  deriving (Semigroup, Monoid)
    via (MonoidMap k [a])

deriving instance Functor (MultiMap k)

fromList :: Ord k => [(k, v)] -> MultiMap k v
fromList = mconcat .
  fmap (MultiMap . fmap pure . uncurry Map.singleton)

This is an not a new idea. It has been proposed to make the union-based Monoid the default for maps. Until that happens, we can use a synonym like the above.