¿Cuáles son las relaciones entre Alternative, MonadPlus (LeftCatch) y MonadPlus (LeftDistributive)?

12

Seguimiento ¿Cuál es un ejemplo de una mónada que es una alternativa pero no una MonadPlus? :

Supongamos que es una mónada. ¿Cuáles son las relaciones betweem m ser una alternativa , un MonadPlusCatch y una MonadPlusDistr ? mmPara cada uno de los seis pares posibles, me gustaría tener una prueba de que uno implica otro, o un contraejemplo de que no.

(Estoy usando

  • MonadPlusCatch para distinguir un MonadPlus que satisfaga la regla Left-Catch :

    mplus (return a) b = return a
    
  • MonadPlusDistr para distinguir un MonadPlus que satisface la regla de distribución izquierda :

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

ver MonadPlus en HaskellWiki .)


Mi conocimiento actual + intuición es que:

  1. MonadPlusDist Alternativa - probablemente cierto - parece sencillo, creo que tengo un boceto de una prueba, lo comprobaré y si es correcto, lo publicaré AndrewC respondió esta parte.
  2. Maybe
  3. 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)
    

    nuevamente lo revisaré y publicaré. (Curiosamente, solo Maybees demostrable, porque podemos analizar si aes Just somethingo Nothing, ver la respuesta de AndrewC antes mencionada).

  4. [][]
  5. []
  6. Maybe
Petr Pudlák
fuente

Respuestas:

8

(porque, como señaló Petr Pudlák, []es un contraejemplo: no satisface MonadPlusCatch pero sí satisface MonadPlusDist , por lo tanto Aplicativo )

Asumido: Leyes MonadPlusDist

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

Para probar: leyes 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 expansión
Supongamos que usamos la derivación estándar de un aplicativo de una mónada, a saber, (<*>) = apy pure = return. Luego

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 expansión
Supongamos que usamos la derivación estándar de un functor de una mónada, a saber (<$>) = liftM. Luego

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 

Prueba

Suponga que ( <+>, m0) cumple con las leyes MonadPlus. Trivialmente, entonces es un monoide.

Dist. Correcta <*>

Lo demostrare

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

porque es más fácil en la notación.

(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

Identidad izquierda <*>

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

según sea necesario.

Dist izquierda <$>

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 >>=

según sea necesario

AndrewC
fuente
1
Excelente. Incluso sospecho que las leyes de la izquierda están implícitas en las leyes de la derecha para cualquier Solicitante , pero hasta ahora no tengo pruebas. La intuición es que f <$>no conlleva ninguna acción idiomática, es pura, por lo que podría ser posible de alguna manera "cambiar de lado".
Petr Pudlák
@ PetrPudlák Actualizado: prueba terminada y agregó su corollory sobre [].
AndrewC
@ PetrPudlák ¿Cree que deberíamos agregar una prueba que []satisfaga MonadPlusCatch? Por el momento, es solo una afirmación sobre HaskellWiki. >>= kse define explícitamente usandofoldr ((++).k)
AndrewC
Supongo que te refieres a MonadPlusDist , ¿no? Creo que podríamos, esto completaría la prueba del corolario.
Petr Pudlák
@ PetrPudlák Oh sí, lo siento. Lo haré
AndrewC
6

De hecho es 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)
       )

La salida es

(Right Nothing, Left "something")

lo que significa que MaybeT Eitherfalla la ley de distribución izquierda de Applicative.


La razón es que

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

ignora g(debido a LeftCatch ) y evalúa solo para

return x `ap` a

pero esto es diferente de lo que evalúa el otro lado:

g `ap` a
Petr Pudlák
fuente