如何在这个 Or 类型上定义一个 mempty ？

Question

在 Haskell Programming from first Principles 一书中，有一个练习要求我在 Or 类型上实例化 Monoid：

data Or a b =
  Fst a
  | Snd b
  deriving (Eq, Show)

之前，我们在实例化时定义了规则Semigroup：

instance Semigroup (Or a b) where
  (Fst _) <> (Fst y) = Fst y
  (Fst _) <> (Snd y) = Snd y
  (Snd x) <> (Fst _) = Snd x
  (Snd x) <> (Snd _)= Snd x

根据上述规则，如果 Fst x 是一个 Monoid，显然它应该是 mempty，其中 x 是 a 类型的任何东西。但是我不知道规则怎么写:

instance (Monoid a, Monoid b) => Monoid (Or a b) where
  mempty = ???  -- Please help me with this, to make every (Fst x) be mempty.
  mappend = (<>)

Answer 1

简而言之：您对(<>)的定义不能用作幺半群的二元运算符。除非可以保证 a（或者 b 如果我们使用 Snd 作为 "neutral element" 的构造函数）只有一个可能的值。

according to the above rules, apparently a Fst x should be the mempty if it was a Monoid.

确切地说，如果它是 monoid [wiki]。但是对于一个幺半群，可以证明存在*恰好一个个恒等元。证明如下：给定有两个中性元素e₁和e₁，则表示e₁⊕e₂=e₁，但同时e₁⊕e₂=e₂（因为 a⊕e=e⊕a=a 与 e 一致元素），所以这意味着 e₁=e₂ 成立，因此两者是一样。

现在在您的 (<>) 定义中没有这样的标识元素。的确，说这个元素是Fst e，那么它应该是：

Fst e <> Fst a = Fst a

它成立（你定义的第一行），但它也应该成立：

Fst a <> Fst e = Fst a

根据您的 (<>) 函数，这仅在 a 为 e 时成立。因此，我们可以将其声明为幺半群的唯一方法是，如果我们只能在 Fst 构造函数中定义 one 值，如所说，例如：

instance Monoid (Or () b) where
    mempty = Fst ()
    mappend = (<>)

因此我们可以得出结论，您的 (<>) 函数不适合作为幺半群的二元运算符。您将需要想出一个不同的二元运算符，其结构可以在幺半群中使用。

现在身份元素仍然可能是 Snd e 形式，但话又说回来：

(Snd x) <> (Snd e) = Snd x
(Snd e) <> (Snd x) = Snd x

应该都成立，而在您的实施中：

(Snd x) <> (Snd _)= Snd x

后者不成立（因为 x 可能不同于 e）。

How to define a `mempty` on this `Or` type?