haskell - 可折叠、Monoid 和 Monad

Question

考虑以下 foldMap 的签名

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

这与“绑定(bind)”非常相似，只是交换了参数:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

因此，在我看来， Foldable 之间肯定存在某种关系。 , Monoid和 Monad ，但我在父类(super class)中找不到它。大概我可以将其中的一个或两个转换为另一个，但我不确定如何。

可以详细说明一下关系吗？

Answer 1

Monoid 和 Monad
哇，这实际上是我们可以使用报价的罕见情况之一:

A monad is just a monoid in the category of endofunctors, [...]

让我们从一个幺半群开始。集合类别 Set 中的幺半群是一组元素 m 与一个空元素 mempty 和一个关联函数 mappend 以组合元素，使得

mempty `mappend` x == x -- for any x
x `mappend` mempty == x -- for any x
-- and
a `mappend` (b `mappend` c) == (a `mappend` b) `mappend` c -- for all a, b, c

注意，幺半群不限于集合，在类别(monads)的类别 Cat 中也存在幺半群，依此类推。基本上任何时候你都有一个关联的二进制操作和它的标识。

现在一个 monad，它是一个“内仿函数类别中的monoid”，具有以下属性:

它是一个内仿函数，这意味着它在 Haskell 类型的类别 * -> * 中具有类型 Hask。

现在，为了更进一步，您必须了解一点类别理论，我将在这里尝试解释:给定两个仿函数 F 和 G ，存在从 F 到 G 的自然转换，只要存在函数 α 使得每个 F a 都可以映射到 G a 。 α 可以是多对一的，但它必须映射 F a 的每个元素。粗略地说，自然变换是仿函数之间的函数。

现在在范畴论中，两个范畴之间可以有很多仿函数。在简化的 View 中，可以说我们甚至不关心哪些仿函数从哪里映射到哪里，我们只关心它们之间的自然转换。

回到 monad，我们现在可以看到“内仿函数范畴中的monoid”必须具有两个自然变换。让我们调用我们的 monad endofunctor M :

从恒等式(endo)仿函数到 monad 的自然转换:

η :: 1 -> M -- this is return

以及从两个单子(monad)组合的自然转换并产生第三个单子(monad):

μ :: M × M -> M

由于 × 是仿函数的组合，我们可以(粗略地说)也写成:

μ :: m a × m a -> m a
μ :: (m × m) a -> m a
μ :: m (m a) -> m a -- join in Haskell

满足这些法律:

μ . M μ == μ . μ M
μ . M η == μ . η M

因此，单子(monad)是内仿函数类别中幺半群的特例。你不能在普通的 Haskell 中为 monad 编写一个 monoid 实例，因为 Haskell 的组合概念太弱了(我认为；这是因为函数被限制在 Hask 并且它比 Cat 弱)。有关详细信息，请参阅 this。

那么 Foldable 呢？

现在至于 Foldable :存在使用自定义二进制函数组合元素的 fold 的定义。现在您当然可以提供任何函数来组合元素，或者您可以使用现有的组合元素概念，即幺半群。再次请注意，这个幺半群仅限于集合幺半群，而不是幺半群的典型定义。

由于幺半群的 mappend 是关联的，因此 foldl 和 foldr 产生相同的结果，这就是幺半群的折叠可以减少到 fold :: Monoid m, Foldable t => t m -> m 的原因。这是幺半群和可折叠之间的明显联系。

@danidiaz已经指出了使用 Applicative和 Monoid使用 Foldable函数 Const之间的连接

在我看来，比较 monad 和 foldable 有点牵强，因为 monad 比 foldable 更强大，因为 foldable 只能根据映射函数累积列表的值，但 monad 绑定(bind)可以在结构上改变上下文( Const a b = Const a) .