考虑以下签名foldMap
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
这与“绑定”非常相似，只是交换了参数：
(>>=) :: Monad m => m a -> (a -> m b) -> m b
因此，在我看来，和之间必须存在某种关系Foldable，但我在超类中找不到它。大概我可以将其中的一个或两个转换为另一个，但我不确定如何。MonoidMonad
可以详细说明一下关系吗？
问问题
2709 次
3 回答
26
Monoid和Monad
哇，这实际上是我们可以使用报价的罕见情况之一：
单子只是内函子类别中的一个幺半群，[...]
让我们从一个幺半群开始。集合类别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
请注意，幺半群不限于集合，在Cat类别（monads）等类别中也存在幺半群。基本上任何时候你都有一个关联的二进制操作和它的标识。
现在一个 monad，它是一个“内函子类别中的monoid”，具有以下属性：
它是一个内函子，这意味着它在Haskell 类型* -> *的类别中具有类型。Hask
现在，为了更进一步，您必须了解一点范畴论，我将在这里尝试解释：给定两个函子F和G，存在从F到的自然转换，G当且仅当存在一个函数α使得每个F a都可以映射到 a G a。α可以是多对一的，但它必须映射F a. 粗略地说，自然变换是函子之间的函数。
现在在范畴论中，两个范畴之间可以有很多函子。在简化的视图中，可以说我们甚至不关心哪些函子从哪里映射到哪里，我们只关心它们之间的自然转换。
回到 monad，我们现在可以看到“内函子范畴中的monoid”必须具有两个自然变换。让我们调用我们的 monad endofunctor M：
从恒等式（endo）函子到 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）。有关更多信息，请参阅此。
怎么样Foldable？
现在至于Foldable：存在fold使用自定义二进制函数组合元素的 s 定义。现在您当然可以提供任何函数来组合元素，或者您可以使用现有的组合元素概念，即幺半群。再次请注意，这个幺半群仅限于集合幺半群，而不是幺半群的典型定义。
由于幺半群mappend是关联的，foldl并且foldr产生相同的结果，这就是为什么幺半群的折叠可以简化为fold :: Monoid m, Foldable t => t m -> m. 这是幺半群和可折叠之间的明显联系。
@danidiaz 已经指出了Applicative,Monoid和Foldable使用Constfunctor之间的联系Const a b = Const a，它的应用实例要求 of 的第一个参数Const是一个幺半群（没有pure（mempty不考虑undefined））。
在我看来，比较 monad 和 foldable 有点牵强，因为 monad 比 foldable 更强大，因为 foldable 只能根据映射函数累积列表的值，但 monad 绑定可以在结构上改变上下文 ( a -> m b)。
于 2016-10-10T07:08:14.877 回答
10
摘要：(>>=)并且traverse看起来很相似，因为它们都是函子的箭头映射，而foldMap（几乎）是专门的traverse.
在我们开始之前，需要解释一些术语。考虑fmap：
fmap :: Functor f => (a -> b) -> (f a -> f b)
HaskellFunctor是从Hask范畴（以 Haskell 函数为箭头的范畴）到自身的函子。在范畴论术语中，我们说 (specialised)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 = f
return <=< f = f
h <=< (g <=< f) = (h <=< g) <=< f
现在，您询问了翻转绑定：
(=<<) :: Monad m => (a -> m b) -> (m a -> m b)
事实证明，这(=<<)是从 Kleisli 范畴的函子到 Hask 的m箭头映射。适用的函子定律(=<<)相当于两个单子定律：
return =<< x = x -- right unit
(g <=< f) =<< x = g =<< (f =<< x) -- associativity
遍历
接下来，我们需要绕道而行Traversable（答案末尾提供了本节结果证明的草图）。首先，我们注意到所有应用函子的a -> f b函数一次获取（而不是每次一个，如指定 Kleisli 类别时）形成一个类别，具有身份和组合。为此，我们还必须采用更宽松的箭头相等，它忽略和样板（这只是必要的，因为我是用伪 Haskell 编写的，而不是正确的数学符号）。更准确地说，我们将考虑任何两个函数可以使用和的任何组合相互转换fIdentityCompose . fmap g . fIdentityComposeIdentityCompose同构为相等的箭头（或者，换句话说，我们不会区分aand Identity a，也不区分f (g a)and Compose f g a）。
让我们将该类别称为“可遍历类别”（因为我现在想不出更好的名称）。Applicative在具体的 Haskell 术语中，此类别中的箭头是一个在任何先前存在的层“下方”添加额外上下文层的函数。现在，考虑traverse：
traverse :: (Traversable t, Applicative f) => (a -> f b) -> (t a -> f (t b))
给定可遍历容器的选择，traverse是函子从“可遍历类别”到自身的箭头映射。它的函子定律相当于可遍历定律。
简而言之，两者(=<<)和traverse都是fmap涉及除Hask之外的类别的函子的类似物，因此它们的类型彼此有点相似也就不足为奇了。
折叠地图
我们仍然需要解释所有这些与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应用函子的。即使Traversableis notFoldable和foldMapDefaultis not ，这也为为什么 的类型类似于 of的类型以及传递性地类似于 offoldMap的类型提供了一个体面的理由。foldMaptraverse(=<<)
作为最后的观察，请注意，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
于 2016-10-10T09:42:39.567 回答
7
当容器是时，和（它是 的超类）Foldable之间存在关系。foldMapApplicativeMonad
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})
我们可以这样foldMap定义：traverse_Constant
foldMap' :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
foldMap' f = getConstant . traverse_ (Constant . f)
我们traverse_用来遍历容器，用 来累积值Constant，然后我们getConstant用来摆脱新类型。
于 2016-10-10T06:11:20.540 回答