haskell monads applicative

haskell - Más diversión con los funtores aplicativos.



monads applicative (5)

Earlier , pregunté sobre la traducción de un código monádico para usar solo la instancia del functor aplicativo de Parsec. Desafortunadamente, recibí varias respuestas que respondían a la pregunta que literalmente hice, pero realmente no me dio mucha información. Así que déjame intentar esto de nuevo ...

Resumiendo mi conocimiento hasta ahora, un funtor aplicativo es algo más restringido que una mónada. En la tradición de "menos es más", restringir lo que el código puede hacer aumenta las posibilidades de manipulación de código loco. En cualquier caso, muchas personas parecen creer que usar aplicativo en lugar de mónada es una solución superior donde es posible.

La clase Applicative se define en Control.Applicative , cuyo listado de Haddock separa de manera útil los métodos de la clase y las funciones de utilidad con una amplia franja de instancias de clase entre ellos, para que sea difícil ver rápidamente todo lo que aparece en la pantalla a la vez. Pero las firmas de tipo pertinentes son

pure :: x -> f x <*> :: f (x -> y) -> f x -> f y *> :: f x -> f y -> f y <* :: f x -> f y -> f x <$> :: (x -> y) -> f x -> f y <$ :: x -> f y -> f x

Tiene perfecto sentido, ¿verdad?

Bueno, Functor ya nos da fmap , que es básicamente <$> . Es decir, dada una función de x a y , podemos asignar un fx a un fy . Applicative agrega dos elementos esencialmente nuevos. Uno es pure , que tiene aproximadamente el mismo tipo de return (y varios otros operadores en varias clases de teoría de categorías). El otro es <*> , que nos permite tomar un contenedor de funciones y un contenedor de entradas y producir un contenedor de salidas.

Usando los operadores anteriores, podemos hacer muy bien algo como

foo <$> abc <*> def <*> ghi

Esto nos permite tomar una función N-aria y generar sus argumentos a partir de N functors de manera que se generalice fácilmente a cualquier N.

Esto ya lo entiendo mucho. Hay dos cosas principales que todavía no entiendo.

Primero, las funciones *> , <* y <$ . De sus tipos, <* = const , *> = flip const , y <$ podría ser algo similar. Sin embargo, presumiblemente esto no describe lo que realmente hacen estas funciones. (??!)

En segundo lugar, cuando se escribe un analizador Parsec, cada entidad analizable suele tener un aspecto similar al siguiente:

entity = do var1 <- parser1 var2 <- parser2 var3 <- parser3 ... return $ foo var1 var2 var3...

Dado que un funtor aplicativo no nos permite vincular los resultados intermedios a las variables de esta manera, me sorprende cómo reunirlos para la etapa final. No he podido envolver mi mente en torno a la idea lo suficiente como para comprender cómo hacerlo.

Las funciones <* y *> son muy simples: funcionan de la misma manera que >> . El <* funcionaría de la misma manera que << excepto << no existe. Básicamente, dado a *> b , primero "haces" a , luego "haces" b y devuelves el resultado de b . Para a <* b , usted primero sigue "do" a luego "do" b , pero devuelve el resultado de a . (Para los significados apropiados de "hacer", por supuesto.)

La función <$ es solo fmap const . Entonces a <$ b es igual a fmap (const a) b . Simplemente tira el resultado de una "acción" y, en su lugar, devuelve un valor constante. La función Control.Monad void , que tiene un tipo Functor f => fa -> f () podría escribirse como () <$ .

Estas tres funciones no son fundamentales para la definición de un funtor aplicativo. ( <$ , de hecho, funciona para cualquier functor.) Esto, de nuevo, es como >> para las mónadas. Creo que están en la clase para que sea más fácil optimizarlos para instancias específicas.

Cuando utiliza functors aplicativos, no "extrae" el valor del functor. En una mónada, esto es lo que hace >>= , y para qué foo <- ... desugars. En su lugar, pasa los valores ajustados a una función directamente usando <$> y <*> . Así que podrías reescribir tu ejemplo como:

foo <$> parser1 <*> parser2 <*> parser3 ...

Si desea variables intermedias, puede usar una instrucción let :

let var1 = parser1 var2 = parser2 var3 = parser3 in foo <$> var1 <*> var2 <*> var3

Como usted supuso correctamente, pure es solo otro nombre para el return . Entonces, para que la estructura compartida sea más obvia, podemos reescribir esto como:

pure foo <*> parser1 <*> parser2 <*> parser3

Espero que esto aclare las cosas.

Ahora solo una pequeña nota. La gente recomienda usar funciones de functor aplicativas para el análisis. Sin embargo, solo debes usarlos si tienen más sentido. Para cosas suficientemente complejas, la versión de la mónada (especialmente con notación-hacer) puede ser más clara. La razón por la que la gente recomienda esto es que

foo <$> parser1 <*> parser2 <*> parser3

es más corto y más legible que

do var1 <- parser1 var2 <- parser2 var3 <- parser3 return $ foo var1 var2 var3

Esencialmente, la f <$> a <*> b <*> c es esencialmente como una aplicación de función levantada. Puede imaginar que <*> es un reemplazo para un espacio (por ejemplo, la aplicación de función) de la misma manera que fmap es un reemplazo para la aplicación de función. Esto también debería darle una idea intuitiva de por qué usamos <$> - es como una versión elevada de $ .

Las respuestas ya dadas son excelentes, pero hay un pequeño punto (ish) que me gustaría explicar explícitamente, y tiene que ver con <* , <$ y *> .

Uno de los ejemplos fue

do var1 <- parser1 var2 <- parser2 var3 <- parser3 return $ foo var1 var2 var3

que también se puede escribir como foo <$> parser1 <*> parser2 <*> parser3 .

Supongamos que el valor de var2 es irrelevante para foo , por ejemplo, es solo un espacio en blanco separado. Entonces tampoco tiene sentido que foo acepte este espacio en blanco solo para ignorarlo. En este caso, foo debería tener dos parámetros, no tres. Usando do notation, puedes escribir esto como:

do var1 <- parser1 parser2 var3 <- parser3 return $ foo var1 var3

Si desea escribir esto usando solo <$> y <*> debería ser algo como una de estas expresiones equivalentes:

(/x _ z -> foo x z) <$> parser1 <*> parser2 <*> parser3 (/x _ -> foo x) <$> parser1 <*> parser2 <*> parser3 (/x -> const (foo x)) <$> parser1 <*> parser2 <*> parser3 (const . foo) <$> parser1 <*> parser2 <*> parser3

¡Pero eso es un poco difícil de conseguir con más argumentos!

Sin embargo, también puede escribir foo <$> parser1 <* parser2 <*> parser3 . Podría llamar a foo la función semántica que se alimenta del resultado de parser1 y parser3 mientras ignora el resultado de parser2 en medio. La ausencia de > está destinada a ser indicativa de la ignorancia.

Si desea ignorar el resultado de parser1 pero usa los otros dos resultados, puede escribir foo <$ parser1 <*> parser2 <*> parser3 , usando <$ lugar de <$> .

Nunca he encontrado mucho uso para *> , normalmente escribiría id <$ p1 <*> p2 para el analizador que ignora el resultado de p1 y simplemente analiza con p2 ; podría escribir esto como p1 *> p2 pero eso aumenta la carga cognitiva para los lectores del código.

He aprendido esta forma de pensar solo para analizadores, pero luego se ha generalizado a Applicative s; pero creo que esta notación viene de la biblioteca uuparsing ; Al menos lo usé en Utrecht hace más de 10 años.

Me gustaría agregar / reformular un par de cosas a las muy útiles respuestas existentes:

Los aplicativos son "estáticos". En pure f <*> a <*> b , b no depende de a , por lo que puede analizarse estáticamente . Esto es lo que intentaba mostrar en mi respuesta a tu pregunta anterior (pero supongo que fallé, lo siento), que dado que en realidad no había una dependencia secuencial de los analizadores, no había necesidad de mónadas.

La diferencia clave que aportan las mónadas a la tabla es (>>=) :: Monad m => ma -> (a -> mb) -> ma , o, alternativamente, join :: Monad m => m (ma) . Tenga en cuenta que cada vez que tenga x <- y dentro de notación, está usando >>= . Estos dicen que las mónadas le permiten usar un valor "dentro" de una mónada para producir una nueva mónada, "dinámicamente". Esto no se puede hacer con un aplicativo. Ejemplos:

-- parse two in a row of the same character char >>= /c1 -> char >>= /c2 -> guard (c1 == c2) >> return c1 -- parse a digit followed by a number of chars equal to that digit -- assuming: 1) `digit`s value is an Int, -- 2) there''s a `manyN` combinator -- examples: "3abcdef" -> Just {rest: "def", chars: "abc"} -- "14abcdef" -> Nothing digit >>= /d -> manyN d char -- note how the value from the first parser is pumped into -- creating the second parser -- creating ''half'' of a cartesian product [1 .. 10] >>= /x -> [1 .. x] >>= /y -> return (x, y)

Por último, los aplicativos habilitan la aplicación de función levantada como lo menciona @WillNess. Para intentar tener una idea de cómo se ven los resultados "intermedios", puede mirar los paralelos entre la aplicación de función normal y levantada. Suponiendo que add2 = (+) :: Int -> Int -> Int :

-- normal function application add2 :: Int -> Int -> Int add2 3 :: Int -> Int (add2 3) 4 :: Int -- lifted function application pure add2 :: [] (Int -> Int -> Int) pure add2 <*> pure 3 :: [] (Int -> Int) pure add2 <*> pure 3 <*> pure 4 :: [] Int -- more useful example [(+1), (*2)] [(+1), (*2)] <*> [1 .. 5] [(+1), (*2)] <*> [1 .. 5] <*> [3 .. 8]

Desafortunadamente, no puede imprimir de manera significativa el resultado de pure add2 <*> pure 3 por la misma razón que no puede para add2 ... frustrante. También es posible que desee ver la Identity y sus instancias de clase de tipos para obtener un manejo de los aplicativos.

Puede ver los funtores, los aplicativos y las mónadas de esta forma: todos llevan una especie de "efecto" y un "valor". (Tenga en cuenta que los términos "efecto" y "valor" son solo aproximaciones; en realidad, no es necesario que existan efectos secundarios o valores, como en Identity o Const .)

  • Con Functor , puede modificar los valores posibles dentro de fmap , pero no puede hacer nada con efectos dentro.

  • Con Applicative , puede crear un valor sin ningún efecto con pure , y puede secuenciar efectos y combinar sus valores en el interior. Pero los efectos y los valores están separados: cuando se secuencian efectos, un efecto no puede depender del valor de uno anterior. Esto se refleja en <* , <*> y *> : secuencia los efectos y combinan sus valores, pero no puede examinar los valores internos de ninguna manera.

    Usted podría definir Applicative usando este conjunto alternativo de funciones:

    fmap :: (a -> b) -> (f a -> f b) pureUnit :: f () pair :: f a -> f b -> f (a, b) -- or even with a more suggestive type (f a, f b) -> f (a, b)

    (donde pureUnit no tiene ningún efecto) y defina pure y <*> partir de ellos (y viceversa). Aquí el pair secuencia dos efectos y recuerda los valores de ambos. Esta definición expresa el hecho de que Applicative es un functor monoidal .

    Ahora considere una expresión arbitraria (finita) que consiste en pair , fmap , pureUnit y algunos valores aplicativos primitivos. Tenemos varias reglas que podemos utilizar:

    fmap f . fmap g ==> fmap (f . g) pair (fmap f x) y ==> fmap (/(a,b) -> (f a, b)) (pair x y) pair x (fmap f y) ==> -- similar pair pureUnit y ==> fmap (/b -> ((), b)) y pair x pureUnit ==> -- similar pair (pair x y) z ==> pair x (pair y z)

    Usando estas reglas, podemos reordenar pair , empujar fmap s hacia afuera y eliminar pureUnit s, por lo que eventualmente dicha expresión se puede convertir en

    fmap pureFunction (x1 `pair` x2 `pair` ... `pair` xn)

    o

    fmap pureFunction pureUnit

    De hecho, en primer lugar, podemos recopilar todos los efectos juntos utilizando el pair y luego modificar el valor resultante utilizando una función pura.

  • Con Monad , un efecto puede depender del valor de un valor monádico anterior. Esto los hace tan poderosos.

Puedo hacer algunas observaciones aquí, espero que sean útiles. Esto refleja mi comprensión de que en sí podría estar equivocado.

pure es inusualmente llamado. Por lo general, las funciones se nombran en referencia a lo que producen, pero en pure x es x que es puro . pure x produce un funtor aplicativo que "transporta" el pure x . "Lleva" por supuesto es aproximado. Un ejemplo: pure 1 :: ZipList Int es un ZipList , que tiene un valor Int puro, 1 .

<*> , *> y <* no son funciones, sino métodos (esto responde a su primera preocupación). f en sus tipos no es general (como lo sería, para las funciones) sino específico, según lo especificado por una instancia específica. Es por eso que de hecho no son solo $ , flip const y const . El tipo especializado f especifica la semántica de combinación . En la programación de estilo aplicativo habitual, combinación significa aplicación. Pero con los funtores, una dimensión adicional está presente, representada por el tipo "portador" f . En fx , hay un "contenido", x , pero también hay un "contexto", f .

El estilo de los "funtores aplicativos" buscó habilitar la programación del "estilo aplicativo", con efectos. Los efectos están representados por funtores, transportistas, proveedores de contexto; "aplicativo" que se refiere al estilo aplicativo normal de la aplicación funcional. Escribir solo fx para denotar la aplicación fue una vez una idea revolucionaria . Ya no había necesidad de sintaxis adicional, no (funcall fx) , no había sentencias CALL , ninguna de estas cosas adicionales - la combinación era aplicación ... No así, con efectos, aparentemente - nuevamente había esa necesidad de la sintaxis especial , cuando Programación con efectos. La bestia asesinada reapareció de nuevo.

Así que vino la Programación Aplicativa con Efectos para hacer de nuevo que la combinación signifique solo aplicación, en el contexto especial (quizás efectivo), si es que realmente lo era. Entonces, para a :: f (t -> r) y b :: ft , la combinación (casi simple) a <*> b es una aplicación de contenido (o tipos t -> r y t ), en un contexto dado (de tipo f ).

La distinción principal de las mónadas es que las mónadas no son lineales . En

do { x <- a ; y <- b x ; z <- c x y ; return (x, y, z) }

el cálculo bx depende de x , y cxy depende tanto de x como de y . Las funciones están anidadas :

a >>= (/x -> b x >>= (/y -> c x y >>= (/z -> .... )))

Si b y c no dependen de los resultados anteriores ( x , y ), esto se puede hacer plano haciendo que las etapas de cómputo se vuelvan a empaquetar, los datos compuestos (esto aborda su segunda preocupación):

a >>= (/x -> b >>= (/y-> return (x,y))) -- `b ` sic >>= (/(x,y) -> c >>= (/z-> return (x,y,z))) -- `c ` >>= (/(x,y,z) -> ..... )

y esto es esencialmente un estilo aplicativo ( b , c son completamente conocidos de antemano, independientemente del valor x producido por a , etc.). Entonces, cuando sus combinaciones crean datos que abarcan toda la información que necesitan para combinaciones adicionales, y no hay necesidad de "variables externas" (es decir, todos los cálculos ya son completamente conocidos, independientemente de los valores producidos por cualquiera de las etapas anteriores), puede Usa este estilo de combinación.

Pero si su cadena monádica tiene ramas que dependen de los valores de dichas variables "externas" (es decir, los resultados de las etapas anteriores del cálculo monádico), entonces no puede crear una cadena lineal a partir de ella. Es esencialmente monádico entonces.

Como ilustración, el primer ejemplo de ese artículo muestra cómo funciona la función "monádica"

sequence :: [IO a] → IO [a] sequence [ ] = return [ ] sequence (c : cs) = do { x <- c ; xs <- sequence cs -- `sequence cs` fully known, independent of `x` ; return (x : xs) }

En realidad, se puede codificar en este estilo "plano y lineal" como

sequence :: (Applicative f) => [f a] -> f [a] sequence [] = pure [] sequence (c : cs) = pure (:) <*> c <*> sequence cs -- (:) x xs

No hay ningún uso aquí para la capacidad de la mónada de ramificarse en los resultados anteriores.

una nota sobre la excelente respuesta de Petr Pudlák : en mi "terminología" aquí, su pair es una combinación sin aplicación . Muestra que la esencia de lo que los Functors aplicativos agregan a los Functors planos, es la capacidad de combinar. Entonces la aplicación se logra con el buen viejo fmap . Esto sugiere funtores combinatorios como quizás un mejor nombre ( actualización: de hecho, "Monoidal Functors" es el nombre).