可折叠，幺半群和单子

Question

可折叠，幺半群和单子

27

考虑以下 foldMap 的签名：

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

这与"bind"非常相似，只是参数交换了一下：

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

在我看来，Foldable、Monoid和Monad之间必须存在某种关系，但我在超类中找不到它。可能我可以将其中一两个转换为另一个，但我不确定如何操作。

能详细说明一下它们之间的关系吗？

- Clinton

1

FYI，“concatMap'”是来自“Data.Foldable”中的“Foldable”类中的“foldMap”。 - ThreeFx

啊，我太傻了，这个问题简化了。 - Clinton

3个回答

10

概述: (>>=) 和 traverse 看起来相似，因为它们都是函子的箭头映射，而 foldMap 是（几乎）一个专门的 traverse。

在开始之前，有一个术语需要解释。考虑 fmap:

fmap :: Functor f => (a -> b) -> (f a -> f b)

一个 Haskell 的 Functor 是从 Hask 类别（Haskell 函数作为箭头的类别）到自身的一个函子。在范畴论术语中，我们说（专门化的）fmap 是这个函子的箭头映射，因为它是将箭头映射到箭头的函子的一部分。（为了完整起见：一个函子由箭头映射加上一个对象映射组成。在这种情况下，对象是 Haskell 类型，因此 Functor 的对象映射将类型映射到类型——更具体地说，Functor 的对象映射是其类型构造函数。）

我们还需要记住范畴和函子定律：

-- Category laws for Hask:
f . id = id
id . f = f
h . (g . f) = (h . g) . f

-- Functor laws for a Haskell Functor:
fmap id = id
fmap (g . f) = fmap g . fmap f

在接下来的内容中，我们将使用除了 Hask 以外的其他类别和不是 Functor 的函子。在这种情况下，我们将通过适当的恒等元素和组合替换 id 和 (.)，通过适当的箭头映射替换 fmap，并且在某些情况下，通过适当的箭头相等性替换 =。

(=<<)

首先让我们从更熟悉的部分开始回答，对于给定的单子 m，a -> m b 函数（也称为 Kleisli 箭头）形成一个类别（m 的 Kleisli 类别），其中 return 是恒等元素，(<=<) 是组合。在这种情况下，三个类别法则就是单子法则：

f <=< return = f
return <=< f = f
h <=<  (g <=<  f) = (h <=<  g) <=<  f

现在，您询问了翻转绑定：

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

原来(=<<)是从Kleisli类别的m到Hask的函子的箭头映射。对于(=<<)应用函子定律相当于两个单子律：

return =<< x = x -- right unit
(g <=< f) =<< x = g =<< (f =<< x) -- associativity

遍历

接下来，我们需要通过 Traversable（本节结果的证明草图在答案末尾提供）进行一个绕路。首先，我们注意到对于所有应用函子 f（与指定 Kleisli 类别时一次一个不同），a -> f b 函数一起形成一个范畴，其中 Identity 为恒等元素，Compose . fmap g . f 为组合。为了使其工作，我们还必须采用更宽松的箭头相等性，忽略 Identity 和 Compose 的样板文件（这只是因为我在伪 Haskell 中编写，而不是使用适当的数学符号）。更准确地说，我们将认为可以使用任何 Identity 和 Compose 同构的任何组合互相转换的两个函数是相等的箭头（或者换句话说，我们不区分 a 和 Identity a，也不区分 f (g a) 和 Compose f g a）。

我们称这个类别为“可遍历类别”（因为我现在想不出更好的名称）。用具体的 Haskell 术语来说，这个类别中的箭头是一种函数，它在任何先前存在的层级“下方”添加了一个额外的 Applicative 上下文层。现在考虑 traverse：

traverse :: (Traversable t, Applicative f) => (a -> f b) -> (t a -> f (t b))

给定可遍历容器的选择，traverse 是从“可遍历类别”到自身的函子的箭头映射。它的函子定律相当于可遍历定律。

简而言之，(=<<) 和 traverse 都是涉及除了Hask以外的范畴的函子的fmap的类比，因此它们的类型有些相似并不令人惊讶。

foldMap

我们仍然需要解释所有这些与foldMap有什么关系。答案是foldMap可以从traverse中恢复（参见danidiaz's answer--它使用traverse_，但由于适用函子是Const m，结果基本相同）。

-- cf. Data.Traversable
foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> (t a -> m)
foldMapDefault f = getConst . traverse (Const . f)

感谢 const/getConst 的同构性，这显然等价于：

foldMapDefault' :: (Traversable t, Monoid m)
                => (a -> Const m b) -> (t a -> Const m (t b))
foldMapDefault' f = traverse f

这只是traverse特化到Monoid m => Const m可应用函子的版本。尽管Traversable不是Foldable，而foldMapDefault也不是foldMap，但这为foldMap的类型与traverse及传递其中的(=<<)的类型相似性提供了合理的证明。

作为最后的观察，注意具有可应用函子Const m的“遍历类别”的箭头对于某些Monoidm并不形成子类别，因为除非Identity是可应用函子的可能选择之一，否则没有身份。这可能意味着从这个答案的角度来看，关于foldMap没有其他有趣的事情可说了。唯一可以给出子类别的单一可应用函子选择是Identity，这一点并不令人惊讶，考虑到使用Identity进行遍历相当于在容器上进行fmap。

附录

以下是我几个月前笔记中粗略的traverse结果推导草图，经过最少的编辑。其中~表示“等同于（某些相关的）同构”。

-- Identity and composition for the "traversable category".
idT = Identity
g .*. f = Compose . fmap g . f

-- Category laws: right identity
f .*. idT ~ f
f .*. idT
Compose . fmap f . idT
Compose . fmap f . Identity
Compose . Identity . f
f -- using getIdentity . getCompose 

-- Category laws: left identity
idT .*. f ~ f
idT .*. f
Compose . fmap Identity . f
f -- using fmap getIdentity . getCompose

-- Category laws: associativity
h .*. (g .*. f) ~ (h .*. g) .*. f
h .*. (g .*. f) -- LHS
h .*. (Compose . fmap g . f)
Compose . fmap h . (Compose . fmap g . f)
Compose . Compose . fmap (fmap h) . fmap g . f
(h .*. g) .*. f -- RHS
(Compose . fmap h . g) .*. f
Compose . fmap (Compose . fmap h . g) . f
Compose . fmap (Compose . fmap h) . fmap g . f
Compose . fmap Compose . fmap (fmap h) . fmap g . f
-- using Compose . Compose . fmap getCompose . getCompose
Compose . Compose . fmap (fmap h) . fmap g . f -- RHS ~ LHS

-- Functor laws for traverse: identity
traverse idT ~ idT
traverse Identity ~ Identity -- i.e. the identity law of Traversable

-- Functor laws for traverse: composition
traverse (g .*. f) ~ traverse g .*. traverse f
traverse (Compose . fmap g . f) ~ Compose . fmap (traverse g) . traverse f 
-- i.e. the composition law of Traversable

- duplode

7

当容器是可折叠的时，foldMap和Applicative（它是Monad的超类）之间存在一种关系。 Foldable有一个名为traverse_的函数，具有以下签名：

traverse_ :: Applicative f => (a -> f b) -> t a -> f ()

可能的一个Applicative是Constant。为了成为一个Applicative，它要求“累加器”参数是一个Monoid：

newtype Constant a b = Constant { getConstant :: a } -- no b value at the term level!

Monoid a => Applicative (Constant a)

例如：

gchi> Constant (Sum 1) <*> Constant (Sum 2) :: Constant (Sum Int) whatever
Constant (Sum {getSum = 3})

我们可以这样用traverse_和Constant来定义 foldMap：

foldMap' :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
foldMap' f = getConstant . traverse_ (Constant . f)

我们使用traverse_遍历容器，使用Constant累加值，然后使用getConstant来摆脱newtype。

- danidiaz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ThreeFx · Accepted Answer

`Monoid`和`Monad`

哇，这实际上是我们可以使用引用的罕见时刻:

一个单子只是一个函子范畴中的幺半群，[...]

让我们从一个幺半群开始。在集合类别Set中的幺半群是具有空元素mempty和可结合函数mappend以组合元素的元素m的集合。

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

请注意，单子并不仅限于集合，范畴“Cat”（单子）中也存在单子等等。基本上，每当您有一个可结合的二元操作和其单位元时，就会出现单子。

现在，单子是指“自函子范畴中的单子”，具有以下属性：

它是一个自函子，这意味着它在Haskell类型的类别“Hask”中具有类型“*-> *”。

现在，要进一步了解，您必须了解一些范畴论知识，我将在此尝试解释：给定两个函子“F”和“G”，如果存在从“F”到“G”的自然变换，则存在一个函数“α”，使得每个“F a”都可以映射到“G a”。α可以是多对一的，但它必须映射“F a”的每个元素。粗略地说，自然变换是两个函子之间的函数。

现在，在范畴论中，两个类别之间可以有许多函子。从简化的角度来看，我们甚至不关心哪些函子从哪里映射到哪里，我们只关心它们之间的自然变换。

回到单子，我们现在可以看到，“自函子范畴中的单子”必须具有两个自然变换。让我们称我们的单子自函子为“M”：

从恒等（endo）函子到单子的自然变换：

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

从两个单子的组合产生一个第三个单子的自然变换：

μ :: 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

因此，单子是范畴中的自函子的幺半群的特例。在正常的Haskell中，你不能为单子编写幺半群实例，因为Haskell的组合概念太弱了（我认为；这是因为函数受到限制，只能使用 Hask，而它比 Cat 弱）。有关更多信息，请参见此处。

现在谈到Foldable：存在使用自定义二元函数组合元素的fold定义。你当然可以提供任何组合元素的函数，或者你可以使用现有的组合元素的概念，即幺半群。请注意，该幺半群限于集合幺半群，而不是范畴定义的幺半群。

由于幺半群的mappend是可结合的，因此foldl和foldr产生相同的结果，这就是为什么将幺半群折叠归纳到fold :: Monoid m, Foldable t => t m -> m的明显联系。这是幺半群和可折叠性之间的明显联系。

@danidiaz已经指出了Applicative、Monoid和Foldable之间的联系，使用Const函子Const a b = Const a，它的应用实例需要Const的第一个参数是幺半群（没有mempty就没有pure（不考虑undefined））。

在我看来，将单子和可折叠性进行比较有点牵强，因为单子比可折叠性更强大，可折叠性只能根据映射函数累积列表的值，但单子绑定可以结构性地改变上下文（a -> m b）。

可折叠，幺半群和单子

Monoid和Monad

(=<<)

遍历

foldMap

附录

`Monoid`和`Monad`