类型的标识是什么？

Question

我有以下数据类型：

data Bull = Fools
  | Twoo
  deriving (Eq, Show)

并使用 Monoid 来实现它：

instance Monoid Bull where
  mempty = Fools
  mappend _ _ = Fools

如您所见，mempty 是恒等律不成立的恒等函数：

*Main> x = Twoo
*Main> mappend mempty x == x

Bull 类型的标识是什么？ Bool类型的身份是什么？

Answer 1

简答：它取决于mappend函数。

What would be the identity of Bull type? What is the identity of Bool type?

类型没有“固有”身份，身份元素仅存在与二元函数有关（此处为mappend），如Wikipedia article says:

In mathematics, an identity element or neutral element is a special type of element of a set with respect to a binary operation on that set, which leaves other elements unchanged when combined with them.

所以这取决于mappend是什么操作。

在 Bool 的情况下，如果我们定义 mappend = (&&)，则 identity 元素是 mempty = True。但是如果我们选择 mappend = (||)，那么 mempty = False.

您的instance Moniod Bull 不正确。由于不能满足属性:

mappend mempty x = x

如果我们选择 Fools 作为 mempty = Fools，那么 mappend Fools Twoo 应该是 Twoo。如果我们选择 mempty = Twoo，那么 mappend Twoo Twoo 仍然不是 Twoo。

Monoid的要点是你必须仔细设计二元运算符。正如Haskell documentation on Monoid所说，它应该满足以下规则：

mappend mempty x = x

mappend x mempty = x

mappend x (mappend y z) = mappend (mappend x y) z

mconcat = foldr mappend mempty

这些规则不是为 Haskell“发明”的：幺半群 是众所周知的 algebraic structure。通常在数学中，幺半群表示为三元组。比如(N,+,0)和N这里的集合（比如自然数），+ 二元函数，以及 0 恒等元。

Answer 2

给定的集合（或类型，在 Haskell 中）没有单一的幺半群。事实上，幺半群中的身份不是由定义它的集合决定的，而是由操作决定的（在 Haskell 中称为 mappend）。例如，整数上的幺半群可以定义为加法（具有标识 0）或乘积（具有标识 1）。

这就是 Sum and the Product 类型存在的原因：因为 Monoid 类型类在 Num a => a 的集合上有多种可能的实现，我们更愿意将其包装成 newtype 并在包装类型上定义 Monoid 实现。

Bool 类型也有类似的构造，All , monoid on booleans under conjuction ((&&)) with identity True, and Any，在析取 ((||)) 下的布尔值上的幺半群具有身份 False。事实上，布尔值可以在许多其他操作（例如 XOR 和 XNOR 门）上形成幺半群。

由于 Bull 类型与 Bool 类型同构（两者都有两个 nullary 构造函数），您可以从 Monoid 在 [=19= 上的实现中获得灵感]，但我们无法通过进一步的上下文来确定哪种实现最适合您的情况。

此外，正如 Anton Xue 提到的，即使您可以为 Bull 定义一个幺半群，它真的有意义吗？你的类型应该代表什么？

Answer 3

这是一个很好的问题，我之前已经玩过好几次了。事实上，这是我想到的 universe 的第一个用途之一，而且我仍然认为它很巧妙。所以让我告诉你！

思路如下：我们将使用 universe 包枚举所有 mempty 和 mappend 的可能实现，然后检查哪个那些满足法律。首先，一些样板文件：

import Data.Universe
import Data.Universe.Instances.Reverse

data Bull = Fools | Twoo deriving (Bounded, Enum, Eq, Ord, Read, Show)
instance Universe Bull
instance Finite Bull

这只是导入包的适当位并定义您的类型。现在，让我们编写幺半群法则。我们希望 mappend 具有关联性；为mappend写(+)，我们可以要求：

associative        (+) = all (\(x,y,z) -> (x+y)+z == x+(y+z)) universe

恒等律彼此非常相似，将我们的 mappend 连接到我们的 mempty（我们在这里称之为 (+) 和 zero）：

leftIdentity  zero (+) = all (\x -> zero+x == x) universe
rightIdentity zero (+) = all (\x -> x+zero == x) universe

一个幺半群应该满足所有三个定律：

monoid (zero, (+)) = associative (+) && leftIdentity zero (+) && rightIdentity zero (+)

现在我们可以通过过滤掉符合规律的幺半群来构建所有幺半群的列表：

monoidsOnBull :: [(Bull, Bull -> Bull -> Bull)]
monoidsOnBull = filter monoid universe

让我们在 ghci 中检查一下：

> mapM_ print monoidsOnBull
(Twoo,[(Fools,[(Fools,Fools),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])
(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Fools)])])
(Twoo,[(Fools,[(Fools,Twoo),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])
(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Twoo)])])

（旁白：我们应该如何阅读此输出？好吧，universe 包通过显示其类型 [(a, b)] 的图来显示类型 a -> b 的函数，即输入和输入对的列表输出。上面输出的每一行都是一个元组，第一部分有一个合适的mempty，第二部分有一个合适的mappend。）

那么这些幺半群 做了什么？让我们一次拿走它们：

(Twoo,[(Fools,[(Fools,Fools),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])

这里 mappend 输出 Fools 除非两个输入都是 Twoo。也就是说，这是 Bull 等同于 (&&)。 (&&) 的标识是 True —— 或 Twoo，在 Bull 的情况下。

(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Fools)])])

如果两个输入相等，mappend 输出 Fools，否则输出 Twoo。您可以将其视为 Bool 上的异或，或 1 位数字上的二进制补码加法。它的身份是Fools（或零）。

(Twoo,[(Fools,[(Fools,Twoo),(Twoo,Fools)]),(Twoo,[(Fools,Fools),(Twoo,Twoo)])])

这一条和上一条一样，只是到处都被否定了。

(Fools,[(Fools,[(Fools,Fools),(Twoo,Twoo)]),(Twoo,[(Fools,Twoo),(Twoo,Twoo)])])

这个和第一个一样，只是处处被否定。它也恰好就像 Bool 上的 (||)，它具有身份 False.

讲座到此结束，但还有另外两个有趣的笔记值得添加。

首先，当您希望 mappend 分别为 (&&) 和 (||) 时，base 提供 All and Any 幺半群。据我所知，没有合适的新类型来获得 xor 或其否定作为 Monoid;但是你可以通过为 Bool 声明一个 Num 实例来伪造它（使用 Word1 的直觉，即 False 是 0 而 True 是 1）通过Sum Bool.

其次，这里的另一个答案是：data Color = Red | Green | Blue 有什么幺半群？我们现在拥有所有的机器来回答这个问题并确认实际上有相当多的幺半群：

> length monoidsOnColor
33

我鼓励您尝试构建将列出所有这些内容的代码，并浏览它们以了解您可以获得哪些见解！

类型的标识是什么？

What is the identity of the type?

haskell

math

monoids