Monad是一个替代品，但不是MonadPlus的例子是什么？ [英] What’s an example of a Monad which is an Alternative but not a MonadPlus?

查看：101
本文介绍了Monad是一个替代品，但不是MonadPlus的例子是什么？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

在对 237428>区分类型类 MonadPlus ，替代和 Monoid


此外，即使 Applicative 是 Monad 的超类，反正你需要 MonadPlus 类，因为服从 p> 

 空<*> m =空

并不足以证明

 空>> = f =空



<因此声称某物是 MonadPlus 比宣称它是另类。

$ b $强b

很明显，任何不是monad的应用函数都会自动成为 Alternative的一个例子不是 MonadPlus ，但Edward Kmett的答案暗示存在一个 monad ，它是一个 Alternative 但不是 MonadPlus ：它的空和< | > 会满足替代定律， 1 但不是 MonadPlus 法则。 2 我不能自己想出一个这样的例子;是否有人知道一个？





1 我无法找到规范的参考对于一套替代法则，但我列出了我认为它们大致在我的回答至由替代输入类及其与其他类型类的关系（搜索右分配短语）。我认为应该持有的四项法律是：
$ b


  1. 正确的分配（< ）： （f <|> g）*< a =（f * a）< |> （g * a）

  2. 正确吸收（对于 <*>< / code>）：   空<> a =空

  3. 左分配（ fmap ）： strong>   f< $> （a< |> b）=（f< $> a）< |> （f <$> b）

  4. 左吸收（对于 fmap ）：    f< $> empty = empty

我也乐于接受更有用的一套替代法律。

2 我知道关于 MonadPlus 法律是什么有一些含糊之处;我很满意一个使用左分布或左捕获的答案，但我会偏好前者。

解决方案

你的答案在 HaskellWiki关于你链接到的MonadPlus ：



< blockquote>

哪些规则？马丁& Gibbons选择Monoid，Left Zero和Left Distribution。这使 [] 一个MonadPlus，但不是可能或 IO 。

所以根据您的喜好选择， Maybe 不是MonadPlus（虽然有一个实例，但它不满足左派）。让我们证明它满足Alternative。



也许是一种替代方案




  1. 正确的分配（<> ）： （f< ; |> g）< *> a =（f * a）< |> （g * a）

案例1： f =没有：

 （无< |> g）*< a =（g）*左 - 身份< |> 
 = Nothing< |> （g * a） - 左身份< |> 
 =（无*> a）< |> （g * a） - 左失败*

案例2： a = Nothing ： 

 （f <|> g）*< Nothing = Nothing  - 正确的失败< *> 
 = Nothing< |>没有 - 左侧标识< |> 
 =（f *>无）< |> （g *无） - 右失败*

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

 （Just h< |> g）*<只是x =只是h *仅x  - 左偏差< |> 
 = Just（h x） - 成功< *> 
 = Just（h x）< |> （g * Just x） - 左偏差< |> 
 =（Just h * Just x）< |> （g * Just x） - 成功*




  1. 正确吸收（对于< ; *> ）： 空<> a = empty

很容易，因为 

  Nothing< *> a =无 - 左失败*




  1. 左分配（ fmap ）： f <$> （a< |> b）=（f< $> a）< |> （f <$> b）

案例1： a =没有 

  f <$> （Nothing< |> b）= f< $> b  - 左身份< |> 
 = Nothing< |> （f< $> b） - 左身份< |> 
 =（f< $>无）< |> （f< $> b） - 失败< $>

案例2： a =只需x 

  f< $> （Just x< |> b）= f< $>仅x  - 左偏差< |> 
 = Just（f x） - 成功< $> 
 = Just（f x）< |> （f b $） - 左偏差< |> 
 =（f< $> Just x）< |> （f< $> b） - 成功< $>




  1. 左吸收（for fmap ）： f <$> empty = empty

另一个简单的方法是：

  f <$> Nothing = Nothing  - 失败< $>



也许不是MonadPlus < h2>

让我们证明 Maybe可能不是MonadPlus的断言：我们需要显示 mplus ab> = k = mplus（a>> = k）（b>> = k）< / code>诀窍在于，一如既往地使用一些绑定来隐藏非常不同的值： 

  a =只是假
b =真正的
 
k真实=只是做到了！ 
k False = Nothing

现在 

  mplus（Just False）（Just True）>> = k = Just False>> = k 
 = k False 
 = Nothing

这里我使用了绑定（>> =） Just False 看起来像是成功的，所以$ c>抢夺失败的胜利（ Nothing ）。 （只是假>> = k）= mplus（k假）（k（假））>>真）
= mplus没什么（只是制造它！）
=只是制造它！

这里失败（ k False ）是计算得早，所以被忽略了，我们做了它！。

因此， mplus ab>> = k = Nothing 但是 mplus（a>> = k）（b>> = k）=Made it！ 。



您可以使用>> = 来查看打破 mplus 对于可能的左偏。



我的证明的有效性：



如果您觉得我没有做足够乏味的派生工作，我会证明我使用的身份：



首先 

  Nothing< |> c = c  - 左身份< |> 
只需d< |> c =仅d  - 左偏差< |>

来自实例声明

  instance其他可能其中
 empty = Nothing 
 Nothing< |> r = r 
 l< |> _ = l

其次 

  f <$> Nothing = Nothing  - 失败< $> 
 f< $>只需x = Just（f x） - 成功< $>来自（< $>）= fmap的

code $和b
$ b $ pre $ $ $ $ $ $ $ $ $ $ $ $ $ $ b $ f $ f $ f $第三，其他三个方面需要更多的工作： p> 

  Nothing< *> c =无 - 左失败* 
 c< *> Nothing = Nothing  - 正确的失败< *> 
只要f <*>只需x = Just（f x） - 成功*

来自定义



<$ p $ （< *>）= 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;返回（f x1 x2）}

实例Monad也许其中
（Just x）>> = k = kx
Nothing>> = _ = Nothing
return = Just

so 

  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（fx）

所以如果 mf 或 mx 都是Nothing，结果也是 Nothing ，而如果 mf =只要f 和 mx = Just x ，结果是 Just（fx）


In his answer to the question "Distinction between typeclasses MonadPlus, Alternative, and Monoid?", Edward Kmett says that

Moreover, even if Applicative was a superclass of Monad, you’d wind up needing the MonadPlus class anyways, because obeying

empty <*> m = empty

isn’t strictly enough to prove that

empty >>= f = empty

So claiming that something is a MonadPlus is stronger than claiming it is Alternative.

It’s clear that any applicative functor which is not a monad is automatically an example of an Alternative which is not a MonadPlus, but Edward Kmett’s answer implies that there exists a monad which is an Alternative but not a MonadPlus: its empty and <|> would satisfy the Alternative laws,1 but not the MonadPlus laws.2 I can’t come up with an example of this by myself; does anybody know of one?

1 I wasn’t able to find a canonical reference for a set of Alternative laws, but I lay out what I believe them to be roughly halfway through my answer to the question "Confused by the meaning of the Alternative type class and its relationship to other type classes" (search for the phrase "right distributivity"). The four laws I believe ought to hold are:

  1. Right distributivity (of <*>):  (f <|> g) <*> a = (f <*> a) <|> (g <*> a)
  2. Right absorption (for <*>):  empty <*> a = empty
  3. Left distributivity (of fmap):  f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
  4. Left absorption (for fmap):  f <$> empty = empty

I’d also happily accept being given a more useful set of Alternative laws.

2 I know that there’s some ambiguity about what the MonadPlus laws are; I’m happy with an answer that uses left distribution or left catch, although I would weakly prefer the former.

解决方案

The clue to your answer is in the HaskellWiki about MonadPlus you linked to:

Which rules? Martin & Gibbons choose Monoid, Left Zero, and Left Distribution. This makes [] a MonadPlus, but not Maybe or IO.

So according to your favoured choice, Maybe isn't a MonadPlus (although there's an instance, it doesn't satisfy left distribution). Let's prove it satisfies Alternative.

Maybe is an Alternative

  1. Right distributivity (of <*>): (f <|> g) <*> a = (f <*> a) <|> (g <*> a)

Case 1: f=Nothing:

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

Case 2: a=Nothing:

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

Case 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. Right absorption (for <*>): empty <*> a = empty

That's easy, because

Nothing <*> a = Nothing    -- left failure <*>

  1. Left distributivity (of fmap): f <$> (a <|> b) = (f <$> a) <|> (f <$> b)

Case 1: a = Nothing

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

Case 2: 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. Left absorption (for fmap): f <$> empty = empty

Another easy one:

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

Maybe isn't a MonadPlus

Let's prove the assertion that Maybe isn't a MonadPlus: We need to show that mplus a b >>= k = mplus (a >>= k) (b >>= k) doesn't always hold. The trick is, as ever, to use some binding to sneak very different values out: 

a = Just False
b = Just True

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

Now

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

here I've used bind (>>=) to snatch failure (Nothing) from the jaws of victory because Just False looked like success.

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

Here the failure (k False) was calculated early, so got ignored and we "Made it!".

So, mplus a b >>= k = Nothing but mplus (a >>= k) (b >>= k) = Just "Made it!".

You can look at this as me using >>= to break the left-bias of mplus for Maybe.

Validity of my proofs:

Just in case you felt I hadn't done enough tedious deriving, I'll prove the identities I used:

Firstly

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

which come from the instance declaration 

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

Secondly

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

which just come from (<$>) = fmap and

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

Thirdly, the other three take a bit more work:

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

Which comes from the definitions

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

so

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)

so if mf or mx are Nothing, the result is also Nothing, whereas if mf = Just f and mx = Just x, the result is Just (f x)

这篇关于Monad是一个替代品，但不是MonadPlus的例子是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆