Instancing Monoid for a Type

Question

I have a Type in Haskell to make a Map have several values associated to a key.

If I compile the following code:

type Mapa k v = Map k [v]

instance Monoid (Mapa k v) where
  --mempty :: Mapa k v
  mempty = DM.empty
  --mappend :: Mapa k v -> Mapa k v -> Mapa k v
  mappend a b = DM.unionWith (++) a b

GHCi will throw:

Illegal instance declaration for `Monoid (Map k [v])'
  (All instance types must be of the form (T a1 ... an)
   where a1 ... an are *distinct type variables*,
   and each type variable appears at most once in the instance head.
   Use -XFlexibleInstances if you want to disable this.)
In the instance declaration for `Monoid (Map k [v])'

Should Mapa be a newtype or a data; or what's the problem?

Answer 1

In this case, you do want to create a newtype. When you just use type, you create a type synonym, which is entirely cosmetic--Mapa k v means exactly the same thing as Map k [v]. You want to create a new type instead because normal maps already have a Monoid instance which would overlap with your new one, leading to confusing behavior.

Since your Mapa type behaves in a fundamentally different way, you want it to be a different type:

newtype Mapa k v = Mapa (DM.Map k [v])

Next, you have to update your instance to work on your new type. This requires two changes: you have to unwrap and rewrap your type synonym and you have to add an Ord k constraint. This second one is necessary because keys to a map have to be comparable for equality and--since the map is actually a tree internally--they have to be ordered. So your new instance will look something like this:

instance Ord k => Monoid (Mapa k v) where
  mempty = Mapa DM.empty
  mappend (Mapa a) (Mapa b) = Mapa $ DM.unionWith (++) a b

Matching against Mapa a lets you access the underlying Map; you can then use normal Map functions on it. After you're done, you just need to wrap it in Mapa again.

Using a different type like this that you have to wrap and unwrap is a little bit inconvenient, but that's the price you have to pay to have different instances. It also makes the fact that Mapa represents something completely different from a normal map much clearer.

One little style hint is that you can define functions using backticks, as infix:

Mapa a `mappend` Mapa b = ...

I think this is clearer for monoids because the monoid operation is normally used as an infix operator.

Finally, the reason you want to use newtype and not data is because newtype has no runtime overhead: it only matters to the typechecker. Conceptually, this makes sense--you're not really creating a new type but rather using the same underlying type in a different way with different instances.