26

Edward Kmettは、 「型クラス、、、および?」の違い</a>に対する彼の回答で、次のように述べています。MonadPlusAlternativeMonoid

さらに、Applicativeが のスーパークラスだったとしても、とにかくMonadそのクラスが必要になることになります。MonadPlus

empty <*> m = empty

厳密にはそれを証明するのに十分ではありません

empty >>= f = empty

したがって、何かが であると主張することは、MonadPlusそれが であると主張することよりも強力ですAlternative。

モナドではないAlternativeアプリカティブ・ファンクターは、自動的にではないan の例になることは明らかですが、エドワード・クメットの答えは、 anであるがaではないモナドMonadPlusが存在することを暗示しています。法律。2 この例を自分で思いつくことはできません。誰か知っていますか？AlternativeMonadPlusempty<|>AlternativeMonadPlus

1一連の法則の正規の参照を見つけることができませんでしたが、「Alternative型クラスの意味と他の型との関係に混乱している」という質問への回答のほぼ半分であると思われるものを並べますクラス」</a> (「右分配性」という語句を検索してください)。私が守らなければならないと信じている4つの法則は次のとおりです。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

あなたの答えの手がかりは、リンク先の MonadPlus に関する HaskellWikiにあります。

どのルール？Martin & Gibbons は、Monoid、Left Zero、Left Distribution を選択しました。これは[]MonadPlus を作成しますが、 Maybeorは作成しませんIO。

したがって、あなたの好みによるとMaybe、MonadPlus ではありません (インスタンスはありますが、左分布を満たしません)。Alternativeを満たすことを証明しましょう。

Maybe代替手段です

  1. 右分配 (の<*>): (f <|> g) <*> a = (f <*> a) <|> (g <*> a)

ケース 1: 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 <$>

ケース 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. 左吸収 ( の場合fmap): f <$> empty = empty

別の簡単なもの：

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

MaybeMonadPlus ではありません

MaybeMonadPlus ではない主張を証明しましょう: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

ここでは、バインドを使用して、成功のように見えたため、勝利のあごから(>>=)失敗 ( ) を奪いました。NothingJust 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!"。

for>>=の左バイアスを打破するために私が使用しているように、これを見ることができます。mplusMaybe

私の証明の妥当性:

面倒な導出を十分に行っていないと思われる場合に備えて、使用したアイデンティティを証明します。

まずは

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)

第 3 に、他の 3 つはもう少し手間がかかります。

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)

したがって、mfまたはmxが Nothing の場合、結果もNothingになりますが、mf = Just fおよびmx = Just xの場合、結果はJust (f x)

于 2012-10-29T15:19:52.140 に答える