Monoid与MonadPlus

Question

我对这两者都很陌生Monads,Monoids而且最近也学到了MonadPlus.从我所看到的,Monoid并MonadPlus都提供了二元结合运算和身份类型.(我用数学的说法称之为半群.)那么Monoid和之间的区别是MonadPlus什么？

Answer 1

阿半群是配备有一个关联的二进制运算的结构.甲独异是与用于二进制操作的单位元半群.

Monads和semigroups

每个monad都必须遵守monad法律.对于我们的案例,重要的是相关性法则.用>>=以下表达:

(m >>= f) >>= g     ?   m >>= (\x -> f x >>= g)

现在让我们应用这个定律来推导出相关性>> :: m a -> m b -> m b:

(m >> n) >> p       ? (m >>= \_ -> n) >>= \_ -> p
                    ? m >>= (\x -> (\_ -> n) x >>= \_ -> p)
                    ? m >>= (\x -> n >>= \_ -> p)
                    ? m >>= (\x -> n >> p)
                    ? m >> (n >> p)

(我们挑选的地方,x以便它不会出现m,n或p).

如果我们专注>>于型m a -> m a -> m a(替代b的a),我们可以看到,对于任何类型a的操作>>形成一个半群m a.因为它对任何a一个都是正确的,我们得到一类索引的半群a.然而,它们通常不是幺半群 - 我们没有身份元素>>.

MonadPlus和幺半群

MonadPlus增加了两个操作,mplus和mzero.MonadPlus法律明确规定mplus,mzero必须形成m a一个任意的幺半群a.再次,我们得到了一类索引的幺半群a.

需要注意的区别MonadPlus和Monoid:Monoid说一些单一类型满足monoidal规则,同时MonadPlus表示,对所有可能的a类型m a满足monoidal法律.这是一个更强大的条件.

因此,一个MonadPlus实例形成两个不同的代数结构:一类半群>>和一类带有mplus和的幺半群mzero.(这不是少见,例如一组自然数大于零种的{1,2,...}形式有半群+和一个独异×和1.)

Answer 2

如果我们有,MonadPlus m那么你说m是a Monad,但是m a(应用于a类型"function"的类型m)是一个幺半群.

如果我们定义(类似于Data.Monoid定义,但我们稍后会使用它)

class                Semigroup a where  (<>) :: a -> a -> a
class Semigroup a => Monoid    a where  zero :: a

然后它有

mzero :: MonadPlus m => m a
mplus :: MonadPlus m => m a -> m a -> m a

具有相当类型和适当的法律

-- left and right identity
mplus a     mzero   ==   a
mplus mzero a       ==   a

-- associativity
(a `mplus` b) `mplus` c   ==   a `mplus` (b `mplus` c)

Monoid如果我们使用,我们甚至可以定义一个Haskell-XFlexibleInstances

{-# LANGUAGE FlexibleInstances #-}
instance MonadPlus m => Semigroup (m a) where  (<>) = mplus
instance MonadPlus m => Monoid    (m a) where  zero = mzero

虽然这些实例与实例重叠Data.Monoid,这可能是它不是标准实例的原因.

像这样的幺半群的另一个例子Alternative m => m a来自Control.Applicative.

Answer 3

我必须强调的很重要的区别:不同于含半幺群,而不像其他的什么答案的状态,MonadPlus并没有提供与关联二元运算和身份的类型.Haskell Report是唯一可以声明标准状态的文档,它没有指定MonadPlus的法则,因此不要求将mplus作为关联或mzero作为其左或右单位.也许作者仍在辩论法律:mplus有很好的理由不是联想的.例如,如果mplus是关联但非交换的,则MonadPlus表示的非确定性搜索计算可能不完整(即,存在我们无法找到的解决方案).由于mplus很少是可交换的,所以如果我们坚持关联性,任何完整的非确定性搜索过程都不能由MonadPlus表示.关于SC的MonadPlus法律问题已经有了详细的讨论:必须mplus永远是联想的