haskell - ¿Qué tan arbitraria es la implementación “ap” para las mónadas?

monads applicative

Question

Actualmente estoy estudiando los vínculos entre la mónada y los funtores aplicativos.

Veo dos implementaciones para ap:

ap m1 m2 = do { f <- m1 ; x <- m2 ; return (f x) }

y

ap m1 m2 = do { x <- m2 ; f <- m1 ; return (f x) }

El segundo es diferente, sin embargo, ¿sería una buena implementación para <*> ?

Me perdí en la prueba de pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

Intento tener una intuición de "qué parte de la mónada es el functor aplicativo" ...

Answer 1

Comencemos con el hecho obvio: tal definición para <*> viola la ley ap en el sentido de que <*> debería ap , donde ap es la definida en la clase Monad , es decir, la primera que publicaste.

Dejando a un lado las trivialidades, por lo que puedo ver, las otras leyes aplicativas deberían mantenerse.

Más concretamente, concentrémonos en la ley de composición que mencionaste. Tu ap "invertido"

(<**>) m1 m2 = do { x <- m2 ; f <- m1 ; return (f x) }

también se puede definir como

(<**>) m1 m2 = pure (flip ($)) <*> m2 <*> m1

donde <*> es el ap "regular".

Esto significa que, por ejemplo,

u <**> (v <**> w) =
  { def. <**> }
pure (flip ($)) <*> (v <**> w) <*> u =
  { def. <**> }
pure (flip ($)) <*> (pure (flip ($)) <*> w <*> v) <*> u =
  { composition law }
pure (.) <*> pure (flip ($)) <*> (pure (flip ($)) <*> w) <*> v <*> u =
  { homomorphism law }
pure ((.) (flip ($))) <*> (pure (flip ($)) <*> w) <*> v <*> u =
  { composition law }
pure (.) <*> pure ((.) (flip ($))) <*> pure (flip ($)) <*> w <*> v <*> u =
  { homomorphism law (x2)}
pure ((.) ((.) (flip ($))) (flip ($))) <*> w <*> v <*> u =
  { beta reduction (several) }
pure (/x f g -> g (f x)) <*> w <*> v <*> u

(Espero haber sacado todo bien)

Intenta hacer algo similar al lado izquierdo.

pure (.) <**> u <**> v <**> w = ...

Answer 2

Hay al menos tres aspectos relevantes a esta pregunta.

1. Dada una instancia de Monad m , ¿cuál es la especificación de su instancia de Superclase de Applicative m necesaria? Respuesta : pure es return , <*> es ap , entonces

   mf <*> ms == do f <- mf; s <- ms; return (f s)

Tenga en cuenta que esta especificación no es una ley de la clase Applicative . Es un requisito en Monad s, para garantizar patrones de uso consistentes.

2. Dada esa especificación (por implementación candidata), es la única implementación aceptable. Respuesta : rotundamente, no . La dependencia de valor permitida por el tipo de >>= veces puede llevar a una ejecución ineficiente: hay situaciones en las que <*> se puede hacer más eficiente que ap porque no es necesario esperar a que termine el primer cálculo antes de poder decir Cuál es el segundo cálculo. La notación "aplicativa do" existe exactamente para explotar esta posibilidad.

3. ¿Alguna otra instancia candidata para el Applicative satisface las leyes de la Applicative , aunque no estén de acuerdo con las instancias requeridas? Respuesta : si. La instancia "hacia atrás" propuesta por la pregunta es tal cosa. De hecho, como lo observa otra respuesta, cualquier aplicativo puede volverse hacia atrás, y el resultado es a menudo una bestia diferente.

Para un ejemplo adicional y un ejercicio para el lector, tenga en cuenta que las listas no vacías son monádicas en la forma en que están familiarizadas con las listas comunes.

  data Nellist x = x :& Maybe (Nellist x)

  necat :: Nellist x -> Nellist x -> Nellist x
  necat (x :& Nothing) ys = x :& Just ys
  necat (x :& Just xs) ys = x :& Just (necat xs ys)

  instance Monad Nellist where
    return x = x :& Nothing
    (x :& Nothing) >>= k = k x
    (x :& Just xs) >>= k = necat (k x) (xs >>= k)

Encuentre al menos cuatro ejemplos de Applicative Nellist distintos que obedezcan las leyes aplicativas.