自由幺半群和幺半群的主要区别是什么?

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]

自由幺半群 到 [a] . 在他关于 category theory for programmers Bartosz Milewski描述道 free monoids

标识元素为空列表,二进制操作为列表串联:

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

直觉上,我认为这个幺半群是“自由的”,因为它是一个你能理解的幺半群 总是 应用,不管您想使用哪种类型的值(就像免费的monad是您可以使用的monad一样) 总是 从任何函子创建)。

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

如果您有两个(或更多的整数),并且您知道您可能想要聚合它们,但是您还没有决定要应用哪种类型的聚合,您可以使用自由幺半群来“聚合”它们-实际上,这意味着将它们放入一个列表中:

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 执行聚合。

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

幺半群 (M,•,1) 是一种数学结构,因此:

1. M 这是一套
2. 1 是……的一员 M
3. • : M * M -> M
4. a•1 = a = 1•a
5. 给定元素 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) 等等

那么什么是集合上的自由幺半群呢 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

很明显,这满足了关于自由幺半群的必要定律 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 迫使我们只有一种方式来代表 和 单元 浓缩 到 Conc [a] 然后我们可以改变 Single x 到 Conc [x] 和 单元 到 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