8

所以，我现在正在学习 Haskell，我想确认或揭穿我对 monoid 的理解。

我从阅读CIS194课程中了解到，monoid 基本上是用于在自定义集上定义自定义二进制操作的“API”。

比起我去告诉自己更多信息，我偶然发现了大量非常令人困惑的教程试图澄清这件事，所以我不再那么确定了。

我有不错的数学背景，但我只是被所有的隐喻弄糊涂了，我正在寻找明确的是/否答案来回答我对幺半群的理解。

4

3 回答 3

8

来自维基百科：

在抽象代数（数学的一个分支）中，幺半群是具有单个关联二元运算和单位元素的代数结构。

我认为你的理解是正确的。从编程的角度来看，Monoid 是一个具有两个必须实现的“方法”的接口。

您的描述中似乎缺少的唯一部分是“身份”，没有它，您描述的是Semigroup。

任何具有“零”或“空”以及组合两个值的方式都可以是 Monoid。需要注意的一点是，一个集合/类型可能以多种方式成为 Monoid，例如通过additionwith identity0或multiplicationwith identity的数字1。

于 2015-09-02T17:34:53.960 回答
5

来自沃尔夫拉姆：

幺半群是在关联二元运算下闭合的集合，并且在 S 中具有单位元素 I，使得对于 S 中的所有 a，Ia=aI=a。

来自维基：

在抽象代数（数学的一个分支）中，幺半群是具有单个关联二元运算和单位元素的代数结构。

所以你的直觉或多或少是正确的。

您只应该记住，它不是为 Haskell 中的“自定义集”定义的，而是一种类型。区别很小（因为类型论中的类型与集合论中的集合非常相似）但是您可以为其定义 Monoid 实例的类型不必是表示数学集合的类型。

换句话说：类型描述了属于该类型的所有值的集合。Monoid 是一个“接口”，它声明任何声称遵守该接口的类型都必须提供一个标识值，一个组合该类型的两个值的二元运算，并且为了使所有通用 Monoid 操作能够满足一些方程，这些方程应该满足按预期工作（例如对 monoid 值列表的通用求和），并且不会产生不合逻辑/不一致的结果。

另外，请注意，该集合（类型）中存在一个标识元素是类型成为 Monoid 类的实例所必需的。

例如，自然数在两个加法下形成一个 Monoid (identity = 0)：

0 + n = n
n + 0 = n

以及乘法（identity = 1）：

1 * n = n
n * 1 = n

++还列出了(identity = )下的幺半群[]：

[] ++ xs = xs
xs ++ [] = xs

同样，类型函数a -> a在组合下形成一个幺半群（恒等式 = id）

id . f = f
f . id = f

所以重要的是要记住 Monoid 不是关于表示集合的类型，而是关于当被视为集合时的类型，可以这么说。

作为构造错误的 Monoid 实例的示例，请考虑：

import Data.Monoid

newtype MyInt = MyInt Int deriving Show

instance Monoid MyInt where
  mempty = MyInt 0
  mappend (MyInt a) (MyInt b) = MyInt (a * b)

如果您现在尝试mconcat使用值列表MyInt，您将始终得到MyInt 0结果，因为标识值0和二元运算*不能很好地配合使用：

λ> mconcat [MyInt 1, MyInt 2]
MyInt 0
于 2015-09-02T17:40:09.713 回答
3

在基本层面上你是对的 - 它只是我们用 表示的二元运算符的 API <>。

然而，幺半群概念的价值在于它与其他类型和类的关系。从文化上讲，我们认为这<>是将相同类型的两个事物连接/附加在一起的自然方式。

考虑这个例子：

{-# LANGUAGE OverloadedStrings #-}

import Data.Monoid

greet x = "Hello, " <> x

该函数greet具有极强的多态性——x可以是字符串、字节字符串或文本，仅举几例。此外，在每种情况下，它基本上都按照您的期望进行 - 它附加x到字符串“Hello,”。

此外，有很多算法可以处理任何可以积累的东西，这些算法非常适合泛化到 Monoid。例如考虑类中的foldMap函数Foldable：

foldMap ::  Monoid m => (a -> m) -> t a -> m

不仅foldMap概括了折叠结构的想法，而且我可以通过替换正确的 Monoid 实例来概括如何执行累加。

如果我有一个t包含 Ints 的可折叠结构，我可以使用foldMapmonoidSum来获得 Ints 的总和，或者使用 withProduct来获得产品等。

最后，使用<>提供了便利。例如，有大量不同的 Set 实现，但对于所有这些实现s <> t来说，始终是两个集合s和t（相同类型）的并集。这使我能够编写与集合的底层实现无关的代码，从而简化我的代码。许多其他数据结构也是如此，例如序列、树、映射、优先级队列等。

于 2015-09-02T17:52:24.820 回答