可折叠，Monoid和Monad [英] Foldable, Monoid and Monad

问题描述

考虑以下签名 foldMap

  foldMap ::（可折叠t，Monoid m）=> （a  - > m） - > t a  - > m 
  

这与bind非常相似，只是参数已交换：

 （>> =）:: Monad m => m a  - > （a  - > m b） - > mb 
  

在我看来，在之间必须有某种关系，可折叠， Monoid 和 Monad ，但我无法在超类中找到它。据推测，我可以将其中的一个或两个转化为另一个，但我不知道如何。

这种关系可以详细吗？

解决方案

Monoid 和 Monad

哇，这实际上是我们可以使用报价的罕见时间之一：

单子只是内生函子类别中的一个幺半群，[/ b]

让我们从一个monoid开始。类集合中的monoid是一组元素 m ，其中一个空元素 mempty 和一个联合函数 mappend 来组合元素，使得



  mempty`mappend` x == x  - 对于任何x 
x`mappend` mempty == x  - 对于任何x 
  - 和
a`mappend`（b `mappend` c）==（一个`mappend` b）`mappend` c  - 所有a，b，c 
  

请注意，monoid不限于集合，类别（monad）等类别 Cat 中也存在monoid。基本上任何时候你都有一个联合二元运算和一个身份。

现在一个monad是一个endofunctors类别中的monoid，具有以下属性： p>



它是一个endofunctor，它意味着它具有类型 * - > * 在类别 Hask Haskell类型中。

现在，我会尝试在这里解释一些类别理论：给定两个函子 F 和 G ，存在从 F 到 G 的自然转换iff存在函数α F a 都可以映射到 G a 。 α可以是多对一的，但它必须映射 F a 的每个元素。粗略地说，自然变换是仿函数之间的函数。

现在在类别理论中，两类之间可以有很多函子。在简化的视图中，可以说我们甚至不关心哪个函子映射到哪里，我们只关心它们之间的自然转换。

回来对单子来说，我们现在可以看到，内部管理者范畴中的幺半群必定带来两种自然变化。我们称之为monad endofunctor M ：

从身份（endo）仿函数到monad的自然转换：

 η:: 1  - > M  - 这是返回
  

并且从两个monad的组合中自然转换并产生第三个：

 μ:: M×M  - > M 
  

因为×是函子的组成，我们可以（粗略地说）也写：

 μ:: ma×ma  - > m a 
μ::（m×m）a  - > m a 
μ:: m（m a） - > ma  - 加入Haskell 
  

符合以下法则：

 μ。 Mμ==μ。 μM 
μ。 Mη==μ。 ηM 
  

因此，monad是endofunctors类别中一个monoid的特例。你不能在正常的Haskell中为Monad编写monoid实例，因为Haskell的组合概念太弱（我认为;这是因为函数被限制为 Hask 并且它更弱比 Cat ）。请参阅此获取更多信息。

Foldable ？

现在至 Foldable ：使用自定义二进制函数来组合元素，存在 fold s的定义。现在你当然可以提供任何功能来组合元素，或者你可以使用现有的组合元素的概念，幺半群。再次请注意，这个幺半群仅限于幺半群，并非幺半群的catorical定义。

由于幺半群的 mappend 是关联的， foldl 和 foldr 产生相同的结果，这就是为什么monids的折叠可以降低到 fold :: Monoid m，Foldable t => t m - >米。这是monoid和foldable之间的一个明显的联系。@ b
$ b @danidiaz已经指出 Applicative ， Monoid 和 Foldable 使用 Const functor Const ab = Const a ，其应用实例需要 Const 的第一个参数为monoid（no pure 没有 mempty （忽略 undefined ））。

在我看来，比较monad和foldable是有点延伸，因为monad比foldable更强大，因为foldable只能根据映射函数累积list值，但monad bind可以在结构上改变上下文（ a - > mb ）。

Consider the following signature of foldMap

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

This is very similar to "bind", just with the arguments swapped:

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

It seems to me that there therefore must be some sort of relationship between Foldable, Monoid and Monad, but I can't find it in the superclasses. Presumably I can transform one or two of these into the other but I'm not sure how.

Could that relationship be detailed?

解决方案

Monoid and Monad

Wow, this is actually one of the rare times we can use the quote:

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

Let's start with a monoid. A monoid in the category Set of sets is a set of elements m with an empty element mempty and an associative function mappend to combine elements such that

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

Note that a monoid is not limited to sets, there also exist monoids in the category Cat of categories (monads) and so on. Basically anytime you have an associative binary operation and an identity for it.

Now a monad, which is a "monoid in the category of endofunctors" has following properties:

It's an endofunctor, that means it has type * -> * in the Category Hask of Haskell types.

Now, to go further you must know a little bit of category theory I will try to explain here: Given two functors F and G, there exists a natural transformation from F to G iff there exists a function α such that every F a can be mapped to a G a. α can be many-to-one, but it has to map every element of F a. Roughly said, a natural transformation is a function between functors.

Now in category theory, there can be many functors between two categories. Ina simplified view it can be said that we don't even care about which functors map from where to where, we only care about the natural transformations between them.

Coming back to monad, we can now see that a "monoid in the category of endofunctors" must posess two natural transformations. Let's call our monad endofunctor M:

A natural transformation from the identity (endo)functor to the monad:

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

And a natural transformation from the conposition of two monads and produce a third one:

μ :: M × M -> M

Since × is the composition of functors, we can (roughly speaking) also write:

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

Satisfying these laws:

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

So, a monad is a special case of a monoid in the category of endofunctors. You can't write a monoid instance for monad in normal Haskell, since Haskell's notion of composition is too weak (I think; This is because functions are restricted to Hask and it's weaker than Cat). See this for more information.

What about Foldable?

Now as for Foldable: there exist definitions of folds using a custom binary function to combine the elements. Now you could of course supply any function to combine elements, or you could use an existing concept of combining elements, the monoid. Again, please note that this monoid restricted to the set monoid, not the catorical definition of monoid.

Since the monoid's mappend is associative, foldl and foldr yield the same result, which is why the folding of monoids can be reduced to fold :: Monoid m, Foldable t => t m -> m. This is an obvious connection between monoid and foldable.

@danidiaz already pointed out the connection between Applicative, Monoid and Foldable using the Const functor Const a b = Const a, whose applicative instance requires the first parameter of Const to be a monoid (no pure without mempty (disregarding undefined)).

Comparing monad and foldable is a bit of a stretch in my opinion, since monad is more powerful than foldable in the sense that foldable can only accumulate a list's values according to a mapping function, but the monad bind can structurally alter the context (a -> m b).

这篇关于可折叠，Monoid和Monad的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！