类型的实例化幺半群

Question

我可以帮您翻译成中文。这段内容是关于 Haskell 编程语言中创建一个 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 应该是 newtype 还是 data？或者说有什么问题吗？

- chamini2

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没有运行时开销：它只关乎类型检查器。从概念上讲，这是有意义的——你并不真正创建一个新类型，而是以一种不同的方式使用相同的基础类型和不同的实例。

- Tikhon Jelvis