为类型实例化Monoid

Question

我在Haskell中有一个Type来使Map有一个与键相关联的值.

如果我编译以下代码:

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将抛出:

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])'

Mapa应该是a newtype还是a data; 或者有什么问题？

Answer 1

在这种情况下,您确实想要创建一个newtype.当你刚刚使用时type,你创建了一个类型同义词,它完全是美化的 - Mapa k v意思是完全相同的Map k [v].您希望创建一个新类型,因为法线贴图已经有一个Monoid与您的新贴图重叠的实例,从而导致混乱的行为.

由于您的Mapa类型以完全不同的方式运行,因此您希望它是不同的类型:

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

接下来,您必须更新实例才能使用新类型.这需要进行两项更改:您必须打开并重新打包类型同义词,并且必须添加Ord k约束.第二个是必要的,因为映射的键必须具有可比性,因为映射实际上是内部的树 - 它们必须被排序.所以你的新实例看起来像这样:

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

匹配Mapa a允许您访问底层Map; 然后你可以使用普通的Map功能.完成后,你只需要Mapa再次包装它.

使用这样的不同类型,你必须包装和解包有点不方便,但这是你必须支付的价格,以拥有不同的实例.它还使得Mapa代表与普通地图完全不同的事实更加清晰.

一个小样式提示是你可以使用反引号来定义函数,作为中缀:

Mapa a `mappend` Mapa b = ...

我认为幺半群更清楚,因为幺半群操作通常用作中缀运算符.

最后,你要使用的原因newtype,而不是data因为newtype没有运行时开销:它只事项向typechecker.从概念上讲,这是有道理的 - 你不是真正创建一个新类型,而是使用相同的底层类型以不同的方式使用不同的实例.