functional programming - programacion - estilo de paso de continuación vs mónadas

monadas leibniz

Question

¿Cuáles son las diferencias entre el estilo de paso de continuación (cps) y las mónadas?

Answer 1

Como se menciona en La esencia de la programación funcional :

La programación con mónadas recuerda mucho a la continuación: estilo de paso (CPS), y este documento explora la relación entre los dos. En cierto sentido, son equivalentes: el CPS surge como un caso especial de una mónada, y cualquier mónada puede incrustarse en el CPS cambiando el tipo de respuesta. Pero el enfoque monádico proporciona una visión adicional y permite un mayor grado de control.

Ese documento es bastante riguroso, y en realidad no amplía la relación entre el CPS y las mónadas. Aquí intento dar un ejemplo informal, pero ilustrativo:

(Nota: a continuación se incluye un entendimiento de Monad por parte de un novato (yo), aunque después de escribirlo, parece ser una de las respuestas de los usuarios de alta reputación. Tómelo con una tonelada de sal)

Considera el clásico Maybe mónada.

-- I don''t use the do notation to make it 
-- look similar to foo below

bar :: Maybe Int
bar =
    Just 5 >>= /x ->
    Just 4 >>= /y ->
    return $ x + y

bar'' :: Maybe Int
bar'' =
    Just 5 >>= /x ->
    Nothing >>= /_ ->
    return $ x

GHCi> bar
Just 9
GHCi> bar''
Nothing

Así que el cálculo se detiene tan pronto como Nothing se encuentra nada, nada nuevo aquí. Intentemos imitar un comportamiento tan monádico utilizando CPS:

Aquí está nuestra función de add vainilla usando CPS. Estamos utilizando todos los Int aquí en lugar del tipo de datos algebric para que sea más fácil:

add :: Int -> Int -> (Int -> Int) -> Int
add x y k = k (x+y)

GHCi> add 3 4 id
7

Observe lo similar que es a una mónada

foo :: Int
foo =
    add 1 2 $ /x -> -- 3
    add x 4 $ /y -> -- 7
    add y 5 $ /z -> -- 12
    z

GHCi> foo
12

DE ACUERDO. Supongamos que queremos que el cómputo tenga un límite de 10. Es decir, cualquier cómputo debe detenerse cuando el siguiente paso dé como resultado un valor mayor que 10. Esto es algo así como decir "un cómputo de Tal vez debe detenerse y devolver Nothing tan pronto como cualquier valor en la cadena es Nothing . Veamos cómo podemos hacerlo escribiendo un "transformador CPS"

cap10 :: (Int -> Int) -> (Int -> Int)
cap10 k = /x ->
    if x <= 10 
    then 
        let x'' = k x in 
        if x'' <= 10 then x'' else x
    else x

foo'' :: Int
foo'' =
    add 1 2 $ cap10 $ /x -> -- 3
    add x 4 $ cap10 $ /y -> -- 7
    add y 5 $ cap10 $ /z -> -- 12
    undefined

GHCi> foo''
7

Observe que el valor de retorno final puede ser undefined , pero eso está bien, porque la evaluación se detiene en el 3er paso ( z ).

Podemos ver que cap10 "envuelve" la continuación normal con alguna lógica adicional. Y eso es muy parecido a lo que una mónada debe: pegar los cálculos junto con un poco de lógica adicional.

Vayamos un paso más allá:

(>>==) :: ((Int -> Int) -> Int) -> (Int -> Int) -> Int
m >>== k = m $ cap10 k

foo'''' :: Int
foo'''' =
    add 1 2 >>== /x -> -- 3
    add x 4 >>== /y -> -- 7
    add y 5 >>== /z -> -- 12
    undefined

GCHi> foo''''
7

Woa! Tal vez acabamos de inventar la mónada Cap10 !

Ahora, si miramos el código fuente de Cont , vemos que Cont es

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

El tipo de runCont es

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

Que se alinea muy bien con el tipo de nuestro >>==

Ahora para responder realmente la pregunta.

Ahora, después de escribir todo esto, releo la pregunta original. El OP pidió la "diferencia": P

Supongo que la diferencia es que el CPS le da a la persona que llama más control, ya que, como de costumbre, el autor de la mónada controla completamente la >>= en una mónada.

Answer 2

Es posible que desee echar un vistazo a este http://blog.sigfpe.com/2008/12/mother-of-all-monads.html

Answer 3

No hay relación, por lo tanto, la pregunta tiene tanto sentido como preguntar acerca de la diferencia entre el color azul y Plutón.

Answer 4

Un artículo interesante que explora el tema es "Programación funcional imperativa" , de Peyton Jones y Wadler.

Es el documento que introdujo la IO monádica y tiene comparaciones con enfoques alternativos, incluido el CPS.

Los autores concluyen:

Así que las mónadas son más poderosas que las continuaciones, ¡pero solo por los tipos! No está claro si esto es solo un artefacto del sistema de tipo Hindley-Milner, o si los tipos están revelando una diferencia de importancia fundamental (nuestra intuición es la última, pero es solo una intuición).