haskell - monadologia - monadas filosofia

¿Cómo y por qué funciona la mónada Haskell Cont? (4)

Así es como se define la mónada Cont:

newtype Cont r a = Cont { runCont :: (a -> r) -> r } instance Monad (Cont r) where return a = Cont ($ a) m >>= k = Cont $ /c -> runCont m $ /a -> runCont (k a) c

¿Podría explicar cómo y por qué funciona esto? ¿Qué está haciendo?

Aquí está fibonacci:

fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)

Imagine que tiene una máquina sin una pila de llamadas, solo permite la recursividad de cola. ¿Cómo ejecutar fib en esa máquina? Podría reescribir fácilmente la función para que funcione en tiempo lineal, en lugar de exponencial, pero eso requiere un poco de conocimiento y no es mecánico.

El obstáculo para hacerlo recursivo es la tercera línea, donde hay dos llamadas recursivas. Solo podemos hacer una sola llamada, que también debe dar el resultado. Aquí es donde entran las continuaciones.

Haremos que fib (n-1) tome un parámetro adicional, que será una función que especifica qué se debe hacer después de calcular su resultado, llámelo x . Se agregará fib (n-2) , por supuesto. Entonces: para calcular fib n calcule fib (n-1) después de eso, si llama al resultado x , calcula fib (n-2) , después de eso, si llama el resultado y , devuelve x+y .

En otras palabras, tienes que decir:

Cómo hacer el siguiente cálculo: " fib'' nc = calcular fib n y aplicar c al resultado"?

La respuesta es que haga lo siguiente: "calcule fib (n-1) y aplique d al resultado", donde dx significa "calcular fib (n-2) y aplicar e al resultado", donde ey significa c (x+y) En codigo:

fib'' 0 c = c 0 fib'' 1 c = c 1 fib'' n c = fib'' (n-1) d where d x = fib'' (n-2) e where e y = c (x+y)

Equivalentemente, podemos usar lambdas:

fib'' 0 = /c -> c 0 fib'' 1 = /c -> c 1 fib'' n = /c -> fib'' (n-1) $ /x -> fib'' (n-2) $ /y -> c (x+y)

Para obtener una identidad real de uso de Fibonacci: fib'' n id . Puedes pensar que la línea fib (n-1) $ ... pasa su resultado x a la siguiente.

Las últimas tres líneas huelen como un bloque do , y de hecho

fib'' 0 = return 0 fib'' 1 = return 1 fib'' n = do x <- fib'' (n-1) y <- fib'' (n-2) return (x+y)

es lo mismo, hasta nuevos tipos, por definición de mónada Cont . Note las diferencias. Hay /c -> al principio, en lugar de x <- ... hay ... $ /x -> c lugar de return .

Intenta escribir factorial n = n * factorial (n-1) en un estilo recursivo de cola usando CPS.

¿Cómo funciona >>= ? m >>= k es equivalente a

do a <- m t <- k a return t

Volviendo a hacer la traducción, con el mismo estilo que en fib'' , obtienes

/c -> m $ /a -> k a $ /t -> c t

simplificando /t -> ct a c

m >>= k = /c -> m $ /a -> k a c

Agregar nuevos tipos que obtienes

m >>= k = Cont $ /c -> runCont m $ /a -> runCont (k a) c

que está en la parte superior de esta página. Es complejo, pero si sabes cómo traducir entre la notación do y el uso directo, no necesitas saber la definición exacta de >>= ! La mónada de continuación es mucho más clara si observas bloqueos.

Mónadas y continuaciones

Si miras este uso de la lista de mónadas ...

do x <- [10, 20] y <- [3,5] return (x+y) [10,20] >>= /x -> [3,5] >>= /y -> return (x+y) ([10,20] >>=) $ /x -> ([3,5] >>=) $ /y -> return (x+y)

eso parece una continuación! De hecho, (>> =) cuando aplica un argumento tiene un tipo (a -> mb) -> mb que es Cont (mb) a . Vea la Madre de todas las mónadas de sigfpe para una explicación. Lo consideraría un buen tutorial de continuación de mónadas, aunque probablemente no era así.

Como las continuidades y las mónadas están tan fuertemente relacionadas en ambas direcciones, creo que lo que se aplica a las mónadas se aplica a las continuaciones: solo el trabajo arduo se las enseñará, y no leerá una metáfora o analogía de un burrito.

Creo que la forma más fácil de controlar la mónada Cont es comprender cómo usar su constructor. Voy a asumir la siguiente definición por ahora, aunque las realidades del paquete de transformers son ligeramente diferentes:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

Esto da:

Cont :: ((a -> r) -> r) -> Cont r a

entonces para construir un valor de tipo Cont ra , necesitamos darle una función a Cont :

value = Cont $ /k -> ...

Ahora, k tiene el tipo a -> r , y el cuerpo de la lambda necesita tener el tipo r . Una cosa obvia que hacer sería aplicar k a un valor de tipo a , y obtener un valor de tipo r . Podemos hacer eso, sí, pero esa es realmente una de las muchas cosas que podemos hacer. Recuerde que el value no necesita ser polimórfico en r , podría ser de tipo Cont String Integer u otra cosa concreta. Asi que:

Podríamos aplicar k a varios valores de tipo a , y combinar los resultados de alguna manera.
Podríamos aplicar k a un valor de tipo a , observar el resultado y luego decidir aplicar k a otra cosa en función de eso.
Podríamos ignorar k completo y solo producir un valor de tipo r nosotros mismos.

Pero que significa todo esto? ¿Qué k termina siendo? Bueno, en un doblock, podríamos tener algo como esto:

flip runCont id $ do v <- thing1 thing2 v x <- Cont $ /k -> ... thing3 x thing4

Aquí está la parte divertida: podemos, en nuestras mentes y de alguna manera informal, dividir el do-block en dos en la aparición del constructor Cont , y pensar en el resto del cómputo completo después de él como un valor en sí mismo. Pero espere, lo que depende depende de qué es x , por lo que es realmente una función de un valor x de tipo a a un valor de resultado:

restOfTheComputation x = do thing3 x thing4

De hecho, este restOfTheComputation es, en términos generales, lo que k termina siendo. En otras palabras, usted llama a k con un valor que se convierte en el resultado x de su cálculo Cont , el resto del cálculo se ejecuta, y luego el r producido vuelve a su lambda como resultado de la llamada a k . Asi que:

si llamó k varias veces, el resto del cálculo se ejecutará varias veces, y los resultados se pueden combinar como lo desee.
si no llamó a k en absoluto, se omitirá el resto del cómputo completo, y la llamada runCont le devolverá cualquier valor de tipo r que haya logrado sintetizar. Es decir, a menos que alguna otra parte de la computación te llame desde su k , y se meta con el resultado ...

Si todavía estás conmigo en este punto, debería ser fácil ver que esto podría ser bastante poderoso. Para aclarar un poco, implementemos algunas clases de tipos estándar.

instance Functor (Cont r) where fmap f (Cont c) = Cont $ /k -> ...

Se nos da un valor Cont con el resultado bind x del tipo a , y una función f :: a -> b , y queremos hacer un valor Cont con el resultado bind fx de tipo b . Bueno, para establecer el resultado del enlace, simplemente llame a k ...

fmap f (Cont c) = Cont $ /k -> k (f ...

Espera, ¿de dónde sacamos x ? Bueno, va a involucrar c , que aún no hemos usado. Recuerde cómo funciona c : recibe una función, y luego llama a esa función con su resultado obligatorio. Queremos llamar a nuestra función con f aplicada a ese resultado de enlace. Asi que:

fmap f (Cont c) = Cont $ /k -> c (/x -> k (f x))

Tada! Siguiente, Applicative :

instance Applicative (Cont r) where pure x = Cont $ /k -> ...

Este es simple. Queremos que el resultado del enlace sea el x que obtenemos.

pure x = Cont $ /k -> k x

Ahora, <*> :

Cont cf <*> Cont cx = Cont $ /k -> ...

Esto es un poco más complicado, pero utiliza esencialmente las mismas ideas que en fmap: primero obtener la función de la primera Cont , haciendo una lambda para que llame:

Cont cf <*> Cont cx = Cont $ /k -> cf (/fn -> ...

A continuación, obtenga el valor x del segundo y haga que fn x el resultado del enlace:

Cont cf <*> Cont cx = Cont $ /k -> cf (/fn -> cx (/x -> k (fn x)))

Monad es muy parecida, aunque requiere runCont o una caja, o permite descomprimir el nuevo tipo.

Esta respuesta ya es bastante larga, así que no entraré en ContT (en resumen: ¡es exactamente lo mismo que Cont ! La única diferencia está en el tipo de constructor de tipos, las implementaciones de todo son idénticas) o callCC (a un combinador útil que proporciona una forma conveniente de ignorar k , implementando la salida anticipada de un subbloque).

Para una aplicación simple y verosímil, prueba la publicación de blog de Edward Z. Yang implementando break etiquetado y continúa para bucles .

Lo primero que debe saber acerca de la mónada de continuación es que, fundamentalmente, no está realmente haciendo nada. ¡Es verdad!

La idea básica de una continuación en general es que representa el resto de un cálculo . Digamos que tenemos una expresión como esta: foo (bar xy) z . Ahora, extraiga solo la parte entre paréntesis, bar xy --esto es parte de la expresión total, pero no es solo una función que podemos aplicar. En cambio, es algo a lo que debemos aplicarle una función. Entonces, podemos hablar del "resto de la computación" en este caso como siendo /a -> foo az , que podemos aplicar a bar xy para reconstruir la forma completa.

Ahora, sucede que este concepto de "el resto de la computación" es útil, pero es incómodo trabajar con él, ya que es algo que está fuera de la subexpresión que estamos considerando. Para que las cosas funcionen mejor, podemos cambiar las cosas de adentro hacia afuera: extraemos la subexpresión que nos interesa y luego la envolvemos en una función que toma un argumento que representa el resto del cálculo: /k -> k (bar xy) .

Esta versión modificada nos brinda mucha flexibilidad, no solo extrae una subexpresión de su contexto, sino que también nos permite manipular ese contexto externo dentro de la subexpresión . Podemos pensar que es una especie de computación suspendida , que nos da un control explícito sobre lo que sucede a continuación. Ahora, ¿cómo podríamos generalizar esto? Bueno, la subexpresión casi no se modifica, así que simplemente reemplácela con un parámetro para la función de adentro hacia afuera, dándonos /xk -> kx --en otras palabras, nada más que la aplicación de función, invertida . Podríamos simplemente escribir flip ($) , o agregar un poco de un sabor exótico a un idioma extranjero y definirlo como un operador |> .

Ahora, sería simple, aunque tedioso y horriblemente ofuscante, traducir cada parte de una expresión a esta forma. Afortunadamente, hay una mejor manera. Como programadores de Haskell, cuando pensamos construir un cálculo dentro de un contexto de fondo, lo siguiente que pensamos es decir, ¿es esto una mónada? Y en este caso la respuesta es sí , sí lo es.

Para convertir esto en una mónada, comenzamos con dos bloques de construcción básicos:

Para una mónada m , un valor de tipo ma representa tener acceso a un valor de tipo a dentro del contexto de la mónada.
El núcleo de nuestros "cálculos suspendidos" es la aplicación de función volteada.

¿Qué significa tener acceso a algo de tipo a en este contexto? Simplemente significa que, para algún valor x :: a , hemos aplicado flip ($) a x , dándonos una función que toma una función que toma un argumento de tipo a , y aplica esa función a x . Digamos que tenemos un cálculo suspendido que contiene un valor de tipo Bool . ¿Qué tipo nos da esto?

> :t flip ($) True flip ($) True :: (Bool -> b) -> b

Entonces, para los cálculos suspendidos, el tipo ma funciona como (a -> b) -> b ... lo cual es quizás un anticlímax, ya que ya sabíamos la firma de Cont , pero por el momento, déjame un comentario.

Algo interesante de notar aquí es que una especie de "inversión" también se aplica al tipo de mónada: Cont ba representa una función que toma una función a -> b y la evalúa como b . Como una continuación representa "el futuro" de una computación, entonces el tipo a en la firma representa en cierto sentido "el pasado".

Entonces, reemplazando (a -> b) -> b con Cont ba , ¿cuál es el tipo monádico para nuestro bloque de construcción básico de aplicación de función inversa? a -> (a -> b) -> b traduce a a -> Cont ba ... el mismo tipo de firma que return y, de hecho, eso es exactamente lo que es.

A partir de ahora, todo se reduce directamente de los tipos: esencialmente no hay una manera sensata de implementar >>= además de la implementación real. ¿Pero qué está haciendo realmente?

En este punto, volvemos a lo que dije inicialmente: la mónada de continuación no está realmente haciendo mucho de nada. Algo de tipo Cont ra es trivialmente equivalente a algo así como simplemente escriba a , simplemente proporcionando id como argumento para el cálculo suspendido. Esto podría llevar a uno a preguntarse si, si Cont ra es una mónada pero la conversión es tan trivial, ¿no debería ser solo una mónada sola? Por supuesto, eso no funciona como está, ya que no hay un constructor de tipos para definir como una instancia de Monad , pero digamos que agregamos un contenedor trivial, como data Id a = Id a . Esto es de hecho una mónada, a saber, la mónada de identidad.

¿Qué hace >>= para la mónada de identidad? La firma de tipo es Id a -> (a -> Id b) -> Id b , que es equivalente a a -> (a -> b) -> b , que es simplemente una aplicación de función simple de nuevo. Habiendo establecido que Cont ra es trivialmente equivalente a Id a , podemos deducir que en este caso también, (>>=) es solo aplicación de función .

Por supuesto, Cont ra es un mundo loco invertido en el que todo el mundo tiene barba de chivo, de modo que lo que sucede realmente implica mezclar las cosas de forma confusa para encadenar dos cálculos suspendidos en un nuevo cómputo suspendido, pero en esencia, no hay nada en realidad pasando inusual! Aplicando funciones a argumentos, ho hum, otro día en la vida de un programador funcional.

EDIT: artículo migrado al siguiente enlace.

He escrito un tutorial que aborda directamente este tema y espero que lo encuentre útil. (¡Ciertamente me ayudó a consolidar mi comprensión!) Es demasiado largo para encajar cómodamente en un tema de Desbordamiento de pila, así que lo migré al Wiki de Haskell.

Por favor mira: MonadCont bajo el capó