Quais são as relações entre Alternative, MonadPlus (LeftCatch) e MonadPlus (LeftDistributive)?

12

Acompanhamento O que é um exemplo de uma Mônada que é uma Alternativa, mas não uma MonadPlus? :

Suponha que é uma mônada. Quais são as relações betweem ser uma alternativa , um MonadPlusCatch e uma MonadPlusDistr ? mmmPara cada um dos seis pares possíveis, eu gostaria de ter uma prova de que um implica outro ou um contra-exemplo de que não.

(Estou a usar

  • MonadPlusCatch para distinguir um MonadPlus que satisfaça a regra de captura esquerda :

    mplus (return a) b = return a
    
  • MonadPlusDistr para distinguir um MonadPlus que satisfaz a regra de distribuição esquerda :

    mplus a b >>= k = mplus (a >>= k) (b >>= k)
    

veja MonadPlus no HaskellWiki .)


Meu conhecimento atual + intuição é que:

  1. MonadPlusDist Alternativa - provavelmente verdadeira - parece simples, acredito que tenho um esboço de uma prova, vou verificá-la e, se estiver correta, publicarei AndrewC respondeu a esta parte.
  2. Alternative MonadPlusDist - false - como AndrewC mostrou em sua resposta : é uma alternativa , mas sabe-se que não é MonadPlusDistMonadPlusCatch ). Maybe
  3. MonadPlusCatch Alternativa - provavelmente falsa - acredito que (ou basicamente qualquer coisa ) deva servir como um contra-exemplo. A razão é que MaybeT (Either e)MaybeT m'

    ((pure x) <|> g) <*> a =    -- LeftCatch
        (pure x) <*> a
    -- which in general cannot be equal to
    ((pure x) <*> a) <|> (g <*> a)
    

    novamente eu vou verificar e postar. (Curiosamente, apenas por Maybeser possível, porque podemos analisar se aé Just somethingou Nothing- veja a resposta de AndrewC acima mencionada.)

  4. Alternativa MonadPlusCatch - provavelmente falso - se provar que MonadPlusDist alternativa , em seguida, irá servidor como um contra-exemplo. (Ou podemos provar explicitamente leis alternativas para .) [][]
  5. MonadPlusDist MonadPlusCatch - false - é um contra-exemplo conhecido. []
  6. MonadPlusCatch MonadPlusDist - false - é um contra-exemplo conhecido. Maybe
Petr Pudlák
fonte

Respostas:

8

MonadPlusDist alternativa é verdadeira.

Corolário: Alternative MonadPlusCatch é falso

(porque, como Petr Pudlak apontou, []é um contra-exemplo - não satisfazer MonadPlusCatch mas não satisfaz MonadPlusDist , daí Applicative )

Assumido: Leis MonadPlusDist

-- (mplus,mzero) is a monoid
mzero >>= k = mzero`                             -- left identity >>=
(a `mplus` b) >>= k  =  (a >>=k) `mplus` (b>>=k) -- left dist mplus

Para provar: Leis Alternativas

-- ((<|>),empty) is a monoid
(f <|> g) <*> a = (f <*> a) <|> (g <*> a) -- right dist <*>
empty <*> a = empty                       -- left identity <*>
f <$> (a <|> b) = (f <$> a) <|> (f <$> b) -- left dist <$>
f <$> empty = empty                       -- empty fmap

<*>lema de expansão
Suponha que usamos a derivação padrão de um aplicativo a partir de uma mônada, a saber, (<*>) = ape pure = return. Então

mf <*> mx = mf >>= \f -> mx >>= \x -> return (f x)

Porque

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

<$>lema de expansão
Suponha que usamos a derivação padrão de um functor a partir de uma mônada, a saber (<$>) = liftM. Então

f <$> mx = mx >>= return . f

Porque

f <$> mx = liftM f mx                    -- premise
         = do { x <- mx; return (f x) }  -- def(liftM)
         = mx >>= \x -> return (f x)     -- desugaring
         = mx >>= \x -> (return.f) x     -- def((.))
         = mx >>= return.f               -- eta-reduction 

Prova

Suponha que ( <+>, m0) satisfaçam as leis do MonadPlus. Trivialmente, então é um monóide.

Dist direito <*>

Vou provar

(mf <+> mg) <*> ma = (mf <*> ma) <+> (mg <*> ma) -- right dist <*>

porque é mais fácil na notação.

(mf <+> mg) <*> ma = (mf <+> mg) >>= \forg -> mx >>= \x -> return (forg x) -- <*> expansion
                   =     (mf >>= \f_g -> mx >>= \x -> return (f_g x))
                     <+> (mg >>= \f_g -> mx >>= \x -> return (f_g x))      -- left dist mplus
                   = (mf <*> mx) <+> (mg <*> mx)                           -- <*> expansion

Identidade esquerda <*>

mzero <*> mx = mzero >>= \f -> mx >>= \x -> return (f x) -- <*> expansion
             = mzero                                     -- left identity >>=

como requerido.

Dist esquerda <$>

f <$> (a <|> b) = (f <$> a) <|> (f <$> b) -- left dist <$>

f <$> (a <+> b) = (a <+> b) >>= return . f              -- <$> expansion
                = (a >>= return.f) <+> (b >>= return.f) -- left dist mplus
                = (f <$> a) <+> (f <$> b)               -- <$> expansion

empty fmap

f <$> mzero = mzero >>= return.f   -- <$> expansion
            = mzero                -- left identity >>=

como requerido

AndrewC
fonte
1
Ótimo. Eu até suspeito que as leis de esquerda estejam implícitas nas leis de direitos de qualquer Candidato , mas não tenho provas até agora. A intuição é que f <$>não realiza nenhuma ação idiomática, é pura, portanto pode ser possível "mudar de lado".
Petr Pudlák
@ PetrPudlák Updated - prova final e adicionou seu corolário sobre [].
31812 AndrewC
@ PetrPudlák Você acha que devemos adicionar uma prova que []satisfaça o MonadPlusCatch? No momento, é apenas uma afirmação no HaskellWiki. >>= ké definida explicitamente usandofoldr ((++).k)
AndrewC
Suponho que você queira dizer MonadPlusDist , não é? Acho que poderíamos, isso completaria a prova do corolário.
Petr Pudlák
@ PetrPudlák Oh sim, eu sinto muito. Vai fazer.
31412 AndrewC
6

Na verdade é MaybeT Either:

{-# LANGUAGE FlexibleInstances #-}
import Control.Applicative
import Control.Monad
import Control.Monad.Trans.Maybe

instance (Show a, Show b) => Show (MaybeT (Either b) a) where
    showsPrec _ (MaybeT x) = shows x

main = print $
    let
        x = id :: Int -> Int
        g = MaybeT (Left "something")
        a = MaybeT (Right Nothing)
    -- print the left/right side of the left distribution law of Applicative:
    in ( ((return x) `mplus` g) `ap` a
       , ((return x) `ap` a) `mplus` (g `ap` a)
       )

A saída é

(Right Nothing, Left "something")

o que significa que MaybeT Eitherfalha na lei de distribuição esquerda de Applicative.


A razão é que

(return x `mplus` g) `ap` a

ignora g(devido ao LeftCatch ) e avalia apenas para

return x `ap` a

mas isso é diferente do que o outro lado avalia:

g `ap` a
Petr Pudlák
fonte