26

Edward Kmett在回答“类型类、和? 之间的区别”</a> 问题时说MonadPlusAlternativeMonoid

此外，即使Applicative是 的超类Monad，你最终还是需要这个MonadPlus类，因为服从

empty <*> m = empty

不足以证明

empty >>= f = empty

因此，声称某物是 aMonadPlus比声称它是 强Alternative。

很明显，任何不是monad 的 applicative functor 都会自动成为 an which is not a的一个例子，但 Edward Kmett 的回答暗示存在一个monad，它是 an但不是 a ：它并且会满足定律，1但不是法律。2 我自己想不出这样的例子；有人知道吗？AlternativeMonadPlusAlternativeMonadPlusempty<|>AlternativeMonadPlus

1我无法找到一组Alternative法律的规范参考，但我列出了我认为它们大约是我对“类型类的含义及其与其他类型的关系感到困惑”问题的答案的一半类”</a>（搜索短语“右分布”）。我认为应该遵守的四项法则是：Alternative

  1. （的）右分配<*>：  (f <|> g) <*> a = (f <*> a) <|> (g <*> a)
  2. 右吸收（对于<*>）：  empty <*> a = empty
  3. 左分布（的fmap）：  f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
  4. 左吸收（对于fmap）：  f <$> empty = empty

我也很乐意接受获得一套更有用的Alternative法律。

2我知道法律是什么有些含糊不清MonadPlus；我对使用左分布或左捕获的答案感到满意，尽管我更喜欢前者。

4

1 回答 1

26

您的答案的线索在HaskellWiki 关于 MonadPlus 您链接到：

有哪些规则？Martin & Gibbons 选择 Monoid、Left Zero 和 Left Distribution。这会[]生成 MonadPlus，但不会生成Maybeor IO。

所以根据你喜欢的选择，Maybe不是 MonadPlus （虽然有一个实例，但它不满足左分布）。让我们证明它满足替代方案。

Maybe是另一种选择

  1. （的）右分配<*>： (f <|> g) <*> a = (f <*> a) <|> (g <*> a)

案例一f=Nothing：：

(Nothing <|> g) <*> a =                    (g) <*> a  -- left identity <|>
                      = Nothing         <|> (g <*> a) -- left identity <|>
                      = (Nothing <*> a) <|> (g <*> a) -- left failure <*>

案例2 a=Nothing：：

(f <|> g) <*> Nothing = Nothing                             -- right failure <*>
                      = Nothing <|> Nothing                 -- left identity <|>
                      = (f <*> Nothing) <|> (g <*> Nothing) -- right failure <*>

案例3：f=Just h, a = Just x

(Just h <|> g) <*> Just x = Just h <*> Just x                      -- left bias <|>
                          = Just (h x)                             -- success <*>
                          = Just (h x) <|> (g <*> Just x)          -- left bias <|>
                          = (Just h <*> Just x) <|> (g <*> Just x) -- success <*>
  1. 右吸收（对于<*>）： empty <*> a = empty

这很容易，因为

Nothing <*> a = Nothing    -- left failure <*>
  1. 左分布（的fmap）： f <$> (a <|> b) = (f <$> a) <|> (f <$> b)

情况1：a = Nothing

f <$> (Nothing <|> b) = f <$> b                        -- left identity <|>
                 = Nothing <|> (f <$> b)          -- left identity <|>
                 = (f <$> Nothing) <|> (f <$> b)  -- failure <$>

案例二：a = Just x

f <$> (Just x <|> b) = f <$> Just x                 -- left bias <|>
                     = Just (f x)                   -- success <$>
                     = Just (f x) <|> (f <$> b)     -- left bias <|>
                     = (f <$> Just x) <|> (f <$> b) -- success <$>
  1. 左吸收（对于fmap）： f <$> empty = empty

另一个简单的：

f <$> Nothing = Nothing   -- failure <$>

Maybe不是 MonadPlus

让我们证明Maybe不是 MonadPlus 的断言：我们需要证明它mplus a b >>= k = mplus (a >>= k) (b >>= k)并不总是成立。与以往一样，诀窍是使用一些绑定将非常不同的值偷偷出来：

a = Just False
b = Just True

k True = Just "Made it!"
k False = Nothing

现在

mplus (Just False) (Just True) >>= k = Just False >>= k
                                     = k False
                                     = Nothing

在这里，我使用 bind从胜利的(>>=)口中抢夺失败（Nothing），因为Just False看起来像成功。

mplus (Just False >>= k) (Just True >>= k) = mplus (k False) (k True)
                                           = mplus Nothing (Just "Made it!")
                                           = Just "Made it!"

这里的失败（k False）是提前计算出来的，所以被忽略了，我们"Made it!"。

所以，mplus a b >>= k = Nothing但是mplus (a >>= k) (b >>= k) = Just "Made it!"。

您可以将其视为我>>=用来打破mplusfor的左偏Maybe。

我的证明的有效性：

以防你觉得我没有做足够乏味的推导，我将证明我使用的身份：

首先

Nothing <|> c = c      -- left identity <|>
Just d <|> c = Just d  -- left bias <|>

来自实例声明 

instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

第二

f <$> Nothing = Nothing    -- failure <$>
f <$> Just x = Just (f x)  -- success <$>

这只是来自(<$>) = fmap和

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

第三，其他三个需要更多的工作：

Nothing <*> c = Nothing        -- left failure <*>
c <*> Nothing = Nothing        -- right failure <*>
Just f <*> Just x = Just (f x) -- success <*>

这来自定义

instance Applicative Maybe where
    pure = return
    (<*>) = ap

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap =  liftM2 id

liftM2  :: (Monad m) => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 f m1 m2          = do { x1 <- m1; x2 <- m2; return (f x1 x2) }

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing
    return              = Just

所以

mf <*> mx = ap mf mx
          = liftM2 id mf mx
          = do { f <- mf; x <- mx; return (id f x) }
          = do { f <- mf; x <- mx; return (f x) }
          = do { f <- mf; x <- mx; Just (f x) }
          = mf >>= \f ->
            mx >>= \x ->
            Just (f x)

所以 if mfor mxare Nothing，结果也是Nothing，而 if mf = Just fand mx = Just x，结果是Just (f x)

于 2012-10-29T15:19:52.140 回答