mkU*_*tra 9 haskell functional-programming category-theory monoids
看起来我非常清楚地了解MonoidHaskell中的内容,但上次我听说过一个叫做免费幺半群的东西.
什么是自由幺半群？它与幺半群有什么关系？
你能在Haskell中提供一个例子吗？
Mar*_*ann 10
在编程环境中,我通常将自由monoid转换为[a].在他关于程序员类别理论的优秀系列文章中,Bartosz Milewski将Haskell中的自由幺半群描述为monoid列表(假设忽略了无限列表中的一些问题).
identity元素是空列表,二进制操作是列表连接:
Prelude Data.Monoid> mempty :: [Int]
[]
Prelude Data.Monoid> [1..3] <> [7..10]
[1,2,3,7,8,9,10]
直觉上,我认为这个monoid是'free',因为它是一个你可以随时应用的monoid ,无论你想要使用什么类型的值(就像免费monad是一个monad,你总是可以从任何functor创建) .
另外,当一个类型存在多个幺半群时,自由幺半群决定使用哪个特定幺半群.例如,对于整数,存在无限多的幺半群,但最常见的是加法和乘法.
如果你有两个(或更多整数),并且你知道你可能想要聚合它们,但是你还没有决定要应用哪种类型的聚合,你可以使用免费的monoid来"聚合"它们 - 实际上,这意味着将它们放在一个列表中:
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
在这两个例子中,我故意选择将每个数字提升为包含更具体的monoid 的类型(Sum,Product),然后用于mconcat执行聚合.
对于加法和乘法,有更简洁的方法可以做到这一点,但我这样做是为了说明如何使用更具体的幺半群来解释自由幺半群.
chi*_*chi 10
正如您所知,monoid是一个具有元素e和操作<>令人满意的集合
e <> x = x <> e = x (identity)
(x<>y)<>z = x<>(y<>z) (associativity)
现在,直觉上,一个自由的幺半群是一个幺半群,它只满足上面的那些方程,显然,它们的所有后果.
例如,Haskell列表monoid ([a], [], (++))是免费的.
相比之下,Haskell和monoid (Sum Int, Sum 0, \(Sum x) (Sum y) -> Sum (x+y))不是自由的,因为它也满足额外的方程.例如,它是可交换的
x<>y = y<>x
这并不是前两个方程式的结果.
请注意,在数学中,可以证明所有自由幺半群都与列表幺半群同构[a].因此,编程中的"自由monoid"只是任何数据结构的一个奇特术语,1)可以转换为列表,然后返回,不丢失信息,2)反之亦然,列表可以转换为它,并且返回,没有信息丢失.
在Haskell中,您可以在心理上用"类似列表类型"替换"自由幺半群".
幺半群(M,\xe2\x80\xa2,1)是一种数学结构，使得：
M是一个集合1是的成员M\xe2\x80\xa2 : M * M -> Ma\xe2\x80\xa21 = a = 1\xe2\x80\xa2aa，我们有。bcMa\xe2\x80\xa2(b\xe2\x80\xa2c) = (a\xe2\x80\xa2b)\xe2\x80\xa2c集合上的自由幺半群M是一个幺半群(M',\xe2\x80\xa2,0)和函数e : M -> M'，对于任何幺半群(N,*,1)，给定一个（集合）映射，f : M -> N我们可以将其扩展到幺半群态射f' : (M',\xe2\x80\xa2,0) -> (N,*,1)，即
f a = f' (e a)\nf' 0 = 1\nf' (a\xe2\x80\xa2b) = (f' a) \xe2\x80\xa2 (f' b)\n换句话说，它是一个没有什么特殊作用的幺半群。
\n一个示例幺半群是运算为加法且标识为 0 的整数。另一个幺半群是整数序列，其运算为串联且标识为空序列。现在加法下的整数不是整数上的自由幺半群。考虑将 映射为整数n序列(n)。然后，为了使其自由，我们需要将其扩展为包含n + mto 的地图(n,m)，即它必须包含0to(0)和(0,0)to 以及 to(0,0,0)等等。
另一方面，如果我们尝试将整数序列视为整数上的自由幺半群，我们会发现它似乎在这种情况下起作用。通过加法将映射扩展为整数，它取序列的和（() 的和为 0）。
\n那么集合上的自由幺半群是什么S？那么我们可以尝试的一件事就是任意二叉树S。在 Haskell 类型中，这看起来像：
data T a = Unit | Single a | Conc (T a) (T a)\n它的身份为Unit,e = Single和(\xe2\x80\xa2) = Conc。
我们可以编写一个函数来展示它是如何免费的：
\n-- here the second argument represents a monoid structure on b\nfree :: (a -> b) -> (b -> b -> b, b) -> T a -> b\nfree f ((*),zero) = f' where\n f' (Single a) = f a\n f' Unit = zero\n f' (Conc a b) = f' a * f' b\n很明显，这满足了 上自由幺半群所需的定律a。除了一个：T a不是幺半群，因为它不太满足定律 4 或 5。
所以现在我们应该问是否可以将其变成一个更简单的自由幺半群，即一个真正的幺半群。答案是肯定的。一种方法是观察Conc Unit a和Conc a UnitSingle a相同。因此让\xe2\x80\x99s 使前两种类型无法表示：
data TInner a = Single a | Conc (TInner a) (TInner a)\ndata T a = Unit | Inner (TInner a)\nConc (Conc a b) c我们可以做的第二个观察是，和之间应该没有区别Conc a (Conc b c)。这是由于上述定律 5。然后我们可以压平我们的树：
data TInner a = Single a | Conc (a,TInner a)\ndata T a = Unit | Inner (TInner a)\n的奇怪结构迫使Conc我们只能用一种方式来表示Single a和Unit。但我们看到我们可以将它们合并在一起：更改Concto的定义Conc [a]，然后我们可以更改Single x为Conc [x]，然后Unit我们Conc []可以得到：
data T a = Conc [a]\n或者我们可以这样写：
\ntype T a = [a]\n操作是：
\nunit = []\ne a = [a]\n(\xe2\x80\xa2) = append\n\nfree f ((*),zero) = f' where\n f' [] = zero\n f' (x:xs) = f x * f' xs\n所以在 Haskell 中，列表类型被称为自由幺半群。
\n| 归档时间： |
|
| 查看次数： |
425 次 |
| 最近记录： |