haskell - Instancing Monoid for a Type -

i have type in haskell make map have several values associated key.

if compile following code:

type mapa k v = map k [v]  instance monoid (mapa k v)   --mempty :: mapa k v   mempty = dm.empty   --mappend :: mapa k v -> mapa k v -> mapa k v   mappend b = dm.unionwith (++) b 

ghci throw:

illegal instance declaration `monoid (map k [v])'   (all instance types must of form (t a1 ... an)    a1 ... *distinct type variables*,    , each type variable appears @ once in instance head.    use -xflexibleinstances if want disable this.) in instance declaration `monoid (map k [v])' 

should mapa newtype or data; or what's problem?

in case, do want create newtype. when use type, create type synonym, entirely cosmetic--mapa k v means same thing map k [v]. want create new type instead because normal maps have monoid instance overlap new one, leading confusing behavior.

since mapa type behaves in fundamentally different way, want different type:

newtype mapa k v = mapa (dm.map k [v]) 

next, have update instance work on new type. requires 2 changes: have unwrap , rewrap type synonym , have add ord k constraint. second 1 necessary because keys map have comparable equality and--since map tree internally--they have ordered. new instance this:

instance ord k => monoid (mapa k v)   mempty = mapa dm.empty   mappend (mapa a) (mapa b) = mapa $ dm.unionwith (++) b 

matching against mapa a lets access underlying map; can use normal map functions on it. after you're done, need wrap in mapa again.

using different type have wrap , unwrap little bit inconvenient, that's price have pay have different instances. makes fact mapa represents different normal map clearer.

one little style hint can define functions using backticks, infix:

mapa `mappend` mapa b = ... 

i think clearer monoids because monoid operation used infix operator.

finally, reason want use newtype , not data because newtype has no runtime overhead: matters typechecker. conceptually, makes sense--you're not creating new type rather using same underlying type in different way different instances.