haskell - ¿Por qué Applicative debería ser una superclase de Monad?

monads fam-proposal

Question

Dado:

Applicative m, Monad m => mf :: m (a -> b), ma :: m a

parece ser considerada una ley que:

mf <*> ma === do { f <- mf; a <- ma; return (f a) }

o más concisamente:

(<*>) === ap

La documentación para Control.Applicative dice que <*> es "aplicación secuencial", y eso sugiere que (<*>) = ap . Esto significa que <*> debe evaluar los efectos secuencialmente de izquierda a derecha, por coherencia con >>= ... Pero eso se siente mal. El artículo original de McBride y Paterson parece implicar que la secuencia de izquierda a derecha es arbitraria:

La mónada IO, y de hecho cualquier Mónada, puede hacerse Aplicable tomando pure = return y <*> = ap . Alternativamente, podríamos usar la variante de ap que realiza los cálculos en el orden opuesto , pero mantendremos el orden de izquierda a derecha en este documento.

Entonces hay dos derivaciones legales, no triviales para <*> que siguen de >>= y return , con comportamiento distinto. Y en algunos casos, ninguna de estas dos derivaciones es deseable.

Por ejemplo, la ley (<*>) === ap obliga a Data.Validation a definir dos tipos de datos distintos: Validation y AccValidation . El primero tiene una instancia de ExceptT similar a ExceptT y una instancia Applicative coherente que tiene una utilidad limitada, ya que se detiene después del primer error. Este último, por otro lado, no define una instancia de Monad , y por lo tanto es libre de implementar un Applicative que, mucho más útil, acumula errores.

Ha habido cierta discusión sobre esto previamente en StackOverflow, pero no creo que haya llegado a la esencia de la pregunta:

¿Por qué debería ser esto una ley?

Las otras leyes para functors, applicatives y mónadas, como identidad, asociatividad, etc., expresan algunas propiedades matemáticas fundamentales de esas estructuras. Podemos implementar varias optimizaciones usando estas leyes y probar cosas sobre nuestro propio código usándolas. Por el contrario, me parece que la ley (<*>) === ap impone una restricción arbitraria sin el correspondiente beneficio.

Por lo que vale, prefiero abandonar la ley a favor de algo como esto:

newtype LeftA m a = LeftA (m a)
instance Monad m => Applicative (LeftA m) where
  pure = return
  mf <*> ma = do { f <- mf; a <- ma; return (f a) }

newtype RightA m a = RightA (m a)
instance Monad m => Applicative (RightA m) where
  pure = return
  mf <*> ma = do { a <- ma; f <- mf; return (f a) }

Creo que captura correctamente la relación entre los dos, sin restringir indebidamente tampoco.

Entonces, algunos ángulos para enfocar la pregunta de:

• ¿Hay alguna otra ley que se relacione con Monad y aplicable?
• ¿Existe alguna razón matemática inherente para que los efectos secuencien para el Applicative de la misma manera que lo hacen para Monad ?
• ¿GHC o cualquier otra herramienta realiza transformaciones de código que asumen / requieren que esta ley sea verdadera?
• ¿Por qué la propuesta Functor-Applicative-Monad considera una cosa abrumadoramente buena? (Las citas serían muy apreciadas aquí).

Y una pregunta extra:

• ¿Cómo se adaptan Alternative y MonadPlus a todo esto?

Nota: edición mayor para aclarar la carne de la pregunta. La respuesta publicada por @duplode cita una versión anterior.

Answer 1

y en mi propia intuición (quizás errónea), dado pure f <*> ma <*> mb , no necesita haber ninguna secuencia predeterminada ya que ninguno de los valores depende el uno del otro.

Los valores no, pero los efectos sí. (<*>) :: t (a -> b) -> ta -> tb significa que debe combinar de alguna manera los efectos de los argumentos para obtener los efectos generales. Si la combinación será conmutativa o no dependerá de cómo se defina la instancia. Por ejemplo, la instancia de Maybe es conmutativa, mientras que la instancia predeterminada, "cross join" para listas no lo es. Por lo tanto, hay casos en los que no puede evitar imponer un cierto orden.

¿Cuáles son las leyes, si las hay, que relacionan a Monad y Applicative?

Si bien es justo decir que pure === return y (<*>) === ap (que citan Control.Applicative ) no son leyes en el sentido fuerte de que, por ejemplo, las leyes de mónadas son así, ayudan a que las instancias no sean sorprendentes . Dado que cada Monad da lugar a una instancia de Applicative (en realidad dos instancias, como usted señala), es natural que la instancia actual de Applicative coincida con lo que la Monad nos da. En cuanto a la convención de izquierda a derecha, seguir el orden de ap y liftM2 (que ya existía cuando se introdujo Applicative , y que refleja el orden impuesto por (>>=) ) fue una decisión sensata. (Tenga en cuenta que, si ignoramos por un momento cuánto (>>=) importa en la práctica, la opción opuesta sería también defendible, como lo haría (<*>) y (=<<) , que tienen tipos análogos , efectos de secuencia en el mismo orden).

¿GHC o cualquier otra herramienta realiza transformaciones de código que asumen / requieren que esta ley sea verdadera?

Eso suena muy poco probable dado que Applicative ni siquiera es una superclase de Monad ( Functor-Applicative-Monad ). Estas "leyes", sin embargo, permiten a los lectores del código realizar las transformaciones, que son igual de importantes.

NB: si necesita revertir la secuencia de los efectos en una instancia Applicative , hay Control.Applicative.Backwards . Control.Applicative.Backwards , como ha señalado Gabriel González. Además, (<**>) voltea los argumentos, pero sigue los efectos de secuencia de izquierda a derecha, por lo que también se puede utilizar para invertir la secuencia. Del mismo modo, (<*) no es flip (*>) , ya que ambos efectos de secuencia van de izquierda a derecha.

Answer 2

Bueno, no estoy muy satisfecho con las respuestas dadas hasta ahora, pero creo que los comentarios adjuntos son un poco más convincentes. Así que resumiré aquí:

Creo que solo hay una instancia de Functor sensible que se deriva de Applicative :

fmap f fa = pure f <*> fa

Suponiendo que sea único, tiene sentido que Functor sea ​​una superclase de Applicative , con esa ley. Del mismo modo, creo que solo hay una instancia de Functor sensible que se desprende de Monad :

fmap f fa = fa >>= return . f

Entonces, de nuevo, tiene sentido que Functor sea ​​una superclase de Monad . La objeción que tuve (y, en realidad, sigo teniendo) es que hay dos instancias Applicative sensatas que se derivan de Monad y, en algunos casos específicos, incluso más que son legales; Entonces, ¿por qué mandar uno?

pigworker (primer autor en el documento original de Applicative ) escribe:

"Por supuesto que no sigue. Es una elección".

(en twitter ): "la notación do es un castigo injusto por trabajar en una mónada; nos merecemos una notación aplicativa"

duplode escribe de manera similar:

"... es justo decir que pure === return y (<*>) === ap no son leyes en el sentido fuerte de que, por ejemplo, las leyes de mónada son tan ..."

"En la idea de LeftA / RightA : hay casos comparables en otras partes de las bibliotecas estándar (por ejemplo, Sum and Product in Data.Monoid ). El problema de hacer lo mismo con Applicative es que la relación de potencia-peso es demasiado baja para justificar la precisión / flexibilidad extra. Los nuevos tipos harían que el estilo de aplicación fuera mucho menos agradable de usar ".

Por lo tanto, estoy feliz de ver esa elección expresada explícitamente, justificada por el simple razonamiento de que hace que los casos más comunes sean más fáciles.

Answer 3

Entre otras cosas, pregunta por qué la propuesta Functor-Applicative-Monad es algo bueno. Una razón es porque la falta de unidad significa que hay mucha duplicación de API. Considere el módulo estándar Control.Monad . Las siguientes son las funciones en ese módulo que esencialmente usan la restricción MonadPlus (no hay ninguna para MonadPlus ):

(>>=) fail (=<<) (>=>) (<=<) join foldM foldM_

Las siguientes son las funciones en ese módulo donde una restricción MonadPlus / MonadPlus podría, por lo que puedo decir, relajarme fácilmente a Applicative / Alternative :

(>>) return mzero mplus mapM mapM_ forM forM_ sequence sequence_ forever
msum filterM mapAndUnzipM zipWithM zipWithM_ replicateM replicateM_ guard
when unless liftM liftM2 liftM3 liftM4 liftM5 ap

Muchos de estos últimos tienen versiones Data.Foldable o Alternative , ya sea en Control.Applicative , Data.Foldable o Data.Traversable , pero ¿por qué necesitan aprender toda esa duplicación en primer lugar?

Answer 4

Solo para el registro, la respuesta a la pregunta en el título es: considere

sequenceA :: Applicative f, Traversable t => t (f a) -> f (t a)
join :: Monad m => m (m a) -> m a

¿Cuál es el tipo de join . sequenceA join . sequenceA ?

1. ATP: Monad m, Traversable m => m (ma) -> ma
2. Situación actual: Applicative m, Monad m, Traversable m => m (ma) -> ma

De acuerdo, join . sequenceA join . sequenceA es una situación inventada, pero ciertamente hay casos en los que necesita una mónada, pero también desea utilizar las operaciones Applicative <*> , *> , <* , <**> , etc. Luego:

• Tener dos restricciones separadas para capturar ambas operaciones es molesto.
• Los nombres Applicative son (IMHO) más bonitos que los de las operaciones tradicionales de mónada.
• Tener dos nombres diferentes, por ejemplo, ap , >> , << , etc., es molesto ("oh, no puedes usar <*> allí, eso es una Monad no Monad "; "oh, tienes que usar <*> allí, eso es un Applicative no una Monad ").
• En mónadas reales, el orden es realmente importante, lo que significa que si >> y *> hacen cosas diferentes, entonces no se puede usar la sintaxis Applicative , porque hará algo que no se espera.

Entonces, pragmáticamente, tener un Applicative para cada Monad que sea compatible con él (en el sentido (<*>) = ap ) es una muy, muy buena idea.