问可折叠、Monoid和Monad

EN

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中也存在么半群，依此类推。基本上，任何时候你都有一个关联的二元操作和它的身份。

现在monad具有以下属性，它是“内函数范畴中的么半群”：

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

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

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

回到monad，我们现在可以看到，“内函数式类别中的么半群”必须有两个自然转换。让我们将monad内部函数命名为M

从identity (endo)functor到monad的自然转换：

η :: 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中为monad编写monoid实例，因为Haskell的组合概念太弱了(我认为；这是因为函数被限制在Hask中，而且它比Cat弱)。有关详细信息，请参阅this。

那Foldable呢？

现在对于Foldable：已经有了fold的定义，使用一个自定义的二进制函数来组合元素。现在，您当然可以提供任何函数来组合元素，也可以使用现有的组合元素的概念，即monoid。同样，请注意，这个么半群仅限于集合么半群，而不是么半群的分类定义。

由于么半群的mappend是结合的，所以foldl和foldr产生相同的结果，这就是为什么么半群的折叠可以简化为fold :: Monoid m, Foldable t => t m -> m。这是monoid和foldable之间的一个明显的联系。

@danidiaz已经使用Const函数器Const a b = Const a指出了Applicative、Monoid和Foldable之间的联系，其应用实例要求Const的第一个参数是么半群(没有pure而没有mempty (忽略undefined))。

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

总结：(>>=)和traverse看起来很相似，因为它们都是函数器的箭头映射，而foldMap (几乎)是一个专门的traverse。

在我们开始之前，有一点术语需要解释。考虑fmap

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

Haskell Functor是从Hask类别( Haskell用作箭头的类别)到其自身的函数器。在范畴理论术语中，我们说(专用的) fmap是这个函数器的箭头映射，因为它是函数器的一部分，将箭头带到箭头。(出于完整性的考虑: functor由一个箭头映射和一个对象映射组成。在本例中，对象是Haskell类型，因此对象映射将类型映射为类型--更具体地说，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的functor。在这种情况下，我们将用适当的标识和组合替换id和(.)，用适当的箭头映射替换fmap，在一种情况下，用适当的箭头相等替换=。

(=<<)

首先从答案中更熟悉的部分开始，对于给定的单体m，a -> m b函数(也称为克莱斯利箭头)形成一个类别(m的克莱斯利类别)，其中return是身份，(<=<)是组合。在本例中，这三个类别法则就是the monad laws

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

现在，您被问及翻转绑定：

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

事实证明，(=<<)是从m的Kleisli类别到Hask的函数器的箭头映射。适用于(=<<)的函子定律相当于两个单子定律：

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

遍历

接下来，我们需要绕道通过Traversable (在答案的末尾提供了本节结果证明的草图)。首先，我们注意到一次获取所有应用函数器f的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都是fmap的类似物，涉及Hask之外的其他类别的函数器，因此它们的类型有点相似也就不足为奇了。

foldMap

我们仍然需要解释所有这些与foldMap有什么关系。答案是可以从traverse恢复foldMap (参见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

这只是专门针对Monoid m => Const m应用函数器的traverse。即使Traversable不是Foldable，foldMapDefault也不是foldMap，这也为为什么foldMap的类型类似于traverse和(=<<)的类型提供了一个很好的理由。

作为最后的观察，请注意，对于某些Monoid m，带有应用函数器Const m的“可遍历类别”的箭头不会形成子类别，因为除非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

当容器为Foldable时，foldMap和Applicative (Monad的超类)之间存在关系。

Foldable有一个名为traverse_的函数，带签名：

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

一种可能的Applicative是Constant。要成为应用程序，它需要“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。