estilo paso continuación vs mónadas

Question

¿Cuáles son las diferencias entre el mantenimiento pasando estilo (cps) y mónadas.

Answer 1

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

Programación con mónadas fuertemente que recuerdan a continuación de paso de estilo (CPS), y este trabajo explora la relación entre los dos. En un sentido, son equivalentes: CPS surge como un caso especial de una mónada, y cualquier mónada pueden estar incrustadas en CPS cambiando el tipo de respuesta. Pero el enfoque monádico ofrece una perspectiva adicional y permite un grado de control.

Ese documento es bastante rigurosa, y en realidad no acaba de ampliar la relación entre CPS y mónadas. Aquí trato de dar un ejemplo informal, pero ilustrativo:

(Nota:. A continuación se muestra un entienden de mónada de un novato (yo mismo), aunque después de escribir que sí parece tener una de la respuesta de los usuarios de alta rep Por favor tome con una tonelada de sal)

Considere el clásico mónada Maybe

-- 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 se encuentre Nothing, nada nuevo aquí. try Vamos a imitar por ejemplo un comportamiento monádico utilizar CPS:

Esta es nuestra función de vainilla add utilizar CPS. Estamos utilizando toda Int aquí en lugar del tipo de datos algebraica 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

Aviso lo similar que es 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

OK. Supongamos que queremos que el cálculo de un tope de 10. Es decir, cualquiera que sea el cálculo que debe parar cuando el siguiente paso resultaría en un valor mayor que 10. Esto es algo así como decir "Tal vez un cálculo debe parar y Nothing regreso tan pronto como sea cualquier valor en la cadena es Nothing). vamos a ver cómo podemos hacerlo escribiendo un "transformador de 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

Tenga en cuenta que el valor de retorno final puede ser undefined, pero que está bien, porque la evaluación se detiene en la tercera etapa (z).

Podemos ver que cap10 "se devuelve" la continuación normal con cierta lógica adicional. Y eso es muy cercano a lo que mónada -. Cálculos de cola junto con un poco de lógica adicional

Vamos a ir 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! Quizás, sólo nos hemos inventado la mónada Cap10!

Ahora bien, si nos fijamos en el código fuente de Cont , vemos que es Cont

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

¿Qué líneas muy bien con el tipo de nuestra >>==

Ahora, para responder a la pregunta en realidad

Ahora después de escribir todo esto lo volvió a leer la pregunta original. El PO pidió la "diferencia": P

Creo que la diferencia es CPS da la persona que llama más control, donde, como suele ser el >>= en una mónada es totalmente controlado por el autor de la mónada.

Answer 2

Es posible que desee echar un vistazo a este http: //blog.sigfpe. com / 2008/12 / madre-de-todo-monads.html

Answer 3

Un interesante trabajo que explora el tema es "programación funcional imperativo", por Peyton Jones y Wadler.

Es el documento que introdujo monádico IO, y tiene comparaciones con otros enfoques, incluyendo CPS.

Los autores concluyen:

Así mónadas son más potentes que las continuaciones, pero sólo debido a los tipos! No está claro si esto es sólo un artefacto del sistema de tipos Hindley-Milner, o si los tipos están revelando una diferencia de importancia fundamental (nuestra propia intuición es esto último -., Pero es sólo una intuición)

Answer 4

No existe una relación, por lo que la pregunta hace tanto sentido como preguntar sobre la diferencia entre el color azul y Plutón.