Free Monoid 和 Monoid 之间的主要区别是什么？

Question

看来我很清楚 Monoid 是什么 Haskell，但上次我听说过一种叫做自由幺半群的东西。

什么是自由幺半群，它与幺半群有什么关系？

能否在 Haskell 中提供示例？

Answer 1

自由幺半群是一种特定类型的幺半群。具体来说，它是通过将一些固定的元素集作为字符然后从这些元素形成所有可能的字符串而得到的幺半群。这些字符串，其底层操作是字符串连接，形成一个幺半群，这个幺半群被称为自由幺半群。

Answer 2

在编程上下文中，我通常将 free monoid 翻译成 [a]。在他关于 Haskell 中的 category theory for programmers, Bartosz Milewski describes free monoids 作为列表幺半群的优秀系列文章中（假设忽略了无限列表的一些问题）。

恒等元为空列表，二元运算为列表拼接：

Prelude Data.Monoid> mempty :: [Int]
[]
Prelude Data.Monoid> [1..3] <> [7..10]
[1,2,3,7,8,9,10]

直觉上，我认为这个幺半群是 'free' 因为它是一个你可以总是应用的幺半群，无论你想使用哪种类型的值（就像免费的 monad 是一个你可以总是从任何仿函数创建的 monad）。

此外，当一个类型存在多个幺半群时，自由幺半群推迟决定使用哪个特定的幺半群。例如，对于整数，存在无限多个幺半群，但最常见的是加法和乘法。

如果您有两个（或更多整数），并且您知道您可能想要对它们进行聚合，但您还没有决定要应用哪种类型的聚合，您可以 'aggregate'他们使用免费的幺半群 - 实际上，这意味着将它们放入列表中：

Prelude Data.Monoid> [3,7]
[3,7]

如果您以后决定要将它们加在一起，那么这是可能的：

Prelude Data.Monoid> getSum $ mconcat $ Sum <$> [3,7]
10

如果您希望将它们相乘，也可以这样做：

Prelude Data.Monoid> getProduct $ mconcat $ Product <$> [3,7]
21

在这两个例子中，我特意选择了将每个数字提升为一个类型（Sum、Product）来体现更具体的幺半群，然后使用 mconcat执行聚合。

对于加法和乘法，有更简洁的方法来执行此操作，但我这样做是为了说明如何使用更具体的幺半群来解释自由幺半群。

Answer 3

一个幺半群 (M,•,1) 是一个数学结构使得：

M是一组
1 是 M
• : M * M -> M
a•1 = a = 1•a
给定 M 中的元素 a、b 和 c，我们有 a•(b•c) = (a•b)•c.

集合 M 上的自由幺半群是一个幺半群 (M',•,0) 和函数 e : M -> M' 这样，对于任何幺半群 (N,*,1)，给定一个（集合）映射 f : M -> N 我们可以将其扩展为幺半群态射 f' : (M',•,0) -> (N,*,1)，即

f a = f' (e a)
f' 0 = 1
f' (a•b) = (f' a) • (f' b)

换句话说，它是一个没什么特别的幺半群。

一个幺半群的例子是操作为加法且标识为0的整数。另一个幺半群是整数序列，其操作为连接且标识为空序列。现在加法下的整数不是整数上的自由幺半群。将映射考虑为从 n 到 (n) 的整数序列。然后，为了免费，我们需要将其扩展到从 n + m 到 (n,m) 的地图，即它必须从 0 到 (0) 和 (0,0) (0,0,0) 等等。

另一方面，如果我们尝试将整数序列视为整数上的自由幺半群，我们会发现它似乎适用于这种情况。将map扩展为整数加法就是取一个序列的和（()的和为0）。

那么集合 S 上的自由幺半群是什么？好吧，我们可以尝试的一件事就是 S 的任意二叉树。在 Haskell 类型中，它看起来像：

data T a = Unit | Single a | Conc (T a) (T a)

它的标识为 Unit、e = Single 和 (•) = Conc。

我们可以写一个函数来展示它是如何免费的：

-- here the second argument represents a monoid structure on b
free :: (a -> b) -> (b -> b -> b, b) -> T a -> b
free f ((*),zero) = f' where
  f' (Single a) = f a
  f' Unit = zero
  f' (Conc a b) = f' a * f' b

很明显，这满足 a 上的自由幺半群所需的法则。除了一个：T a 不是幺半群，因为它不完全满足法则 4 或 5。

所以现在我们应该问我们是否可以把它变成一个更简单的自由幺半群，即一个真正的幺半群。答案是肯定的。一种方法是观察 Conc Unit a 和 Conc a Unit 以及 Single a 应该相同。所以让我们让前两种类型不可表示：

data TInner a = Single a | Conc (TInner a) (TInner a)
data T a = Unit | Inner (TInner a)

我们可以做的第二个观察是 Conc (Conc a b) c 和 Conc a (Conc b c) 之间应该没有区别。这是由于上述第 5 条。然后我们可以展平我们的树：

data TInner a = Single a | Conc (a,TInner a)
data T a = Unit | Inner (TInner a)

Conc 的奇怪结构迫使我们只能用一种方式来表示 Single a 和 Unit。但是我们看到我们可以将它们合并在一起：将 Conc 的定义更改为 Conc [a] 然后我们可以将 Single x 更改为 Conc [x]，将 Unit 更改为 Conc [] 所以我们有：

data T a = Conc [a]

或者我们可以这样写：

type T a = [a]

操作是：

unit = []
e a = [a]
(•) = append

free f ((*),zero) = f' where
  f' [] = zero
  f' (x:xs) = f x * f' xs

所以在Haskell中，列表类型称为自由幺半群。

Answer 4

如您所知，幺半群是一个包含元素 e 和操作 <> 满足

的集合

e <> x = x <> e = x  (identity)
(x<>y)<>z = x<>(y<>z)  (associativity)

现在，直觉上，自由幺半群是一个仅满足上述等式及其所有结果的幺半群。

例如，Haskell 列表幺半群 ([a], [], (++)) 是免费的。

相比之下，Haskell 和幺半群 (Sum Int, Sum 0, \(Sum x) (Sum y) -> Sum (x+y)) 不是自由的，因为它还满足其他方程。例如，它是可交换的

x<>y = y<>x

这并不符合前两个等式。

请注意，在数学上可以证明，所有自由幺半群都与列表幺半群同构 [a]。因此，"free monoid" 在编程中只是任何数据结构的一个奇特术语，它 1) 可以转换为列表，然后返回，不会丢失信息，2) 反之亦然，列表可以转换为它, 然后返回，没有信息丢失。

在 Haskell 中，您可以在心里将 "free monoid" 替换为 "list-like type"。

Free Monoid 和 Monoid 之间的主要区别是什么？

What is the main difference between Free Monoid and Monoid?

haskell

functional-programming

category-theory

monoids