24

我对两者都很陌生Monads，Monoids最近还了解到MonadPlus. 从我所见，Monoid两者MonadPlus都提供了一种具有关联二元运算和标识的类型。Monoid（我将其称为数学术语中的半群。） 那么和之间有什么区别MonadPlus？

4

3 回答 3

34

半群是配备关联二元运算的结构。幺半群是具有二元运算的单位元的半群。

单子和半群

每个 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对于任何类型，该操作在 上形成一个半群。由于任何 都为真，因此我们得到一类由 索引的半群。但是，它们通常不是幺半群——我们没有.aa>>m aaa>>

MonadPlus 和类半群

MonadPlus增加了两个操作，mplus并且mzero. MonadPlus法律明确规定了这一点，mplus并且mzero必须m a为任意a. 再次，我们得到了一类由 索引的幺半群a。

MonadPlus注意和之间的区别Monoid:Monoid表示某些单一类型满足幺半群规则，而MonadPlus表示对于所有可能a的类型都m a满足幺半群规则。这是一个更强大的条件。

所以一个MonadPlus实例形成了两种不同的代数结构：一类具有 的半群和一类具有和>>的幺半群。（这并不少见，例如，大于零的自然数集形成了一个半群，其中和 一个幺半群，以及。）mplusmzero{1,2,...}+×1

于 2013-06-12T08:58:13.777 回答
12

如果我们有，MonadPlus m那么你会说m是 a Monad，但是m a（应用a到类型 "function"产生的类型m）是一个幺半群。

如果我们定义（类似于Data.Monoid's 的定义，但我们稍后会使用它）

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.

于 2013-06-12T02:52:40.173 回答
7

我必须强调非常重要的区别：与 Monoid 不同，与其他答案不同，MonadPlus没有提供具有关联二元运算和标识的类型。Haskell 报告是唯一可以声称标准状态的文档，它没有指定 MonadPlus 的定律，因此不需要 mplus 是关联的或 mzero 是它的左或右单元。也许作者们仍在争论这些法律：mplus 有很好的理由不具有关联性。例如，如果 mplus 是关联的但不可交换的，那么 MonadPlus 所代表的非确定性搜索计算就不能完成（即存在我们找不到的解）。由于 mplus 是可交换的很少见，如果我们坚持关联性，任何完整的非确定性搜索过程都不能用 MonadPlus 表示。已经详细讨论了 SC 上的 MonadPlus 法律这个问题：mplus 必须始终是关联的

于 2014-11-14T10:24:39.650 回答