可折叠,Monoid和Monad

Question

考虑以下签名 foldMap

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

这与"绑定"非常相似,只是交换了参数:

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

在我看来,有因此必须有某种关系的Foldable,Monoid和Monad,但在超我找不到它.据推测,我可以将其中的一个或两个转换为另一个,但我不确定如何.

这种关系可以详细说明吗？

Answer 1

Monoid 和 Monad

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

monad只是endofunctors类别中的幺半群,[...]

让我们从一个幺半群开始吧.Set集合类别中的monoid 是一组元素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

注意,幺半群不限于集合,Cat类别(monad)类别中也存在幺半群等.基本上任何时候你都有一个关联二进制操作和它的身份.

现在,monad是一个"endofunctors类别中的monoid",具有以下属性:

这是一个endofunctor,这意味着它已键入* -> *的范畴HaskHaskell的类型.

现在,为了更进一步,你必须知道我将在这里解释的一些类别理论:给定两个仿函数,F并且G存在从if F到Gif 的自然转换,存在一个函数?,使得每个F a都可以映射到a G a.?可以是多对一的,但它必须映射每个元素F a.粗略地说,自然变换是算子之间的函数.

现在在类别理论中,两个类别之间可以存在许多仿函数.在简化的视图中,可以说我们甚至不关心哪个仿函数从何处映射到哪里,我们只关心它们之间的自然变换.

回到monad,我们现在可以看到"endofunctors类别中的monoid"必须进行两次自然变换.我们打电话给我们的monad endofunctor M:

从身份(endo)仿函数到monad的自然转换:

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

从两个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是endofunctors类别中monoid的特例.你不能在正常的Haskell中为monad写一个monoid实例,因为Haskell的组合概念太弱了(我认为;这是因为函数被限制Hask而且它比它弱Cat).有关更多信息,请参阅此

怎么样Foldable？

现在至于Foldable:存在fold使用自定义二元函数来组合元素的s的定义.现在你可以提供任何组合元素的功能,或者你可以使用现有的组合元素概念,即monoid.再次请注意,这个幺半群仅限于集合幺半群,而不是幺半群的catorical定义.

由于幺半群mappend是相关的,foldl并foldr产生相同的结果,这就是为什么可以减少幺半群的折叠fold :: Monoid m, Foldable t => t m -> m.这是monoid和foldable之间的明显联系.

@danidiaz已经指出之间的连接Applicative,Monoid并Foldable使用该Const函子Const a b = Const a,其应用性实例需要的第一个参数Const是一个独异(无pure无mempty(不考虑undefined)).

比较monad和foldable在我看来有点拉伸,因为monad比可折叠更强大,因为foldable只能根据映射函数累积列表的值,但是monad绑定可以在结构上改变context(a -> m b).

Answer 2

摘要:(>>=)和traverse外观相似,因为它们都是仿函数的箭头映射,同时foldMap是(几乎)是专业traverse.

在我们开始之前,有一些术语需要解释.考虑fmap:

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

Haskell Functor是一个来自Hask类别(带有Haskell函数的类别,如箭头)的仿函数.在类别理论术语中,我们说(专门的)fmap是这个仿函数的箭头映射,因为它是将箭头带到箭头的仿函数的一部分.(为了完整起见:仿函数由箭头映射和对象映射组成.在这种情况下,对象是Haskell类型,因此对象映射将类型转换为类型 - 更具体地说,a的对象映射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以外的类别和非Functors的函子.在这种情况下,我们将替换id和(.)通过适当的身份和组合物中,fmap由相应的箭头映射,并且在一种情况下,=由箭头的适当平等.

(= <<)

从答案中更熟悉的部分开始,对于给定的monad m,a -> m b函数(也称为Kleisli箭头)形成一个类别(Kleisli类别m),具有return身份和(<=<)组合.在这种情况下,三类法律只是单一法律:

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

现在,你问到翻转绑定:

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

事实证明,这(=<<)是一个从Kleisli类m到Hask的仿函数的箭头映射.适用于(=<<)两个monad法则的仿函数法律:

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

横过

接下来,我们需要绕道而行Traversable(在答案的最后提供了本节结果证明的草图).首先,我们注意到,a -> f b对功能的所有应用性仿函数f采取一次(如各时刻而不是一个,指定Kleisli类别时)形成一个类别,与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.答案是foldMap可以从中恢复traverse(参见danidiaz的答案 - 它使用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对于某些Monoid 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

Answer 3

当容器是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})

我们可以定义foldMap来讲traverse_,并Constant通过这种方式:

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

我们使用traverse_遍历容器,累积值Constant,然后我们getConstant用来摆脱newtype.