continuazione passando stile vs monadi

Question

Quali sono le differenze tra la continuazione di passaggio stile (CPS) e monadi.

Answer 1

Come menzionato in L'essenza della programmazione funzionale :

Programmazione con monadi ricorda fortemente continuazione-passing style (CPS), e questo lavoro esplora il rapporto tra i due. In un certo senso sono equivalenti: CPS si pone come un caso particolare di una monade e ogni monade possono essere incorporati in CPS cambiando il tipo di risposta. Ma l'approccio monadica fornisce una visione ulteriore e permette un grado di controllo.

Questo documento è molto rigorosa, e in realtà non del tutto espande sul rapporto tra CPS e monadi. Qui cerco di dare un esempio informali, ma illustrativo:

. (Nota: Qui di seguito è un capire di Monad da un novizio (me stesso), anche se dopo la scrittura in quanto sembra assomigliare a uno di rispondere a quelle high-rep degli utenti Si prega di prendere con una tonnellata di sale)

Si consideri il classico Maybe monade

-- 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

Quindi, il calcolo si ferma non appena Nothing si incontra, niente di nuovo qui. prova di Let per imitare un tale comportamento monadica utilizzando CPS:

Ecco la nostra funzione di vaniglia add utilizzare CPS. Stiamo utilizzando tutti Int qui invece del tipo di dati algebrica per rendere più facile:

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

GHCi> add 3 4 id
7

Si noti come simile è quello di una monade

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

GHCi> foo
12

OK. Supponiamo che vogliamo che il calcolo deve essere limitato a 10. Vale a dire, qualunque sia il calcolo deve fermarsi quando il passo successivo si tradurrebbe in un valore maggiore di 10. Questo è un po 'come dire "un calcolo Forse deve fermarsi e Nothing ritorno al più presto qualsiasi valore della catena è Nothing). Vediamo come possiamo farlo scrivendo un "trasformatore di 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

Si noti che il valore di ritorno finale può essere undefined, ma che è bene, perché la valutazione si ferma al 3 ° gradino (z).

Possiamo vedere che cap10 "avvolge" il proseguimento normale con una certa logica in più. E questo è molto vicino a quello che Monade a -. Calcoli colla insieme con una logica più

go passo uno di Let ulteriormente:

(>>==) :: ((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! Forse abbiamo appena inventato la monade Cap10!

Ora, se guardiamo il codice di cont , vediamo che Cont è

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

Il tipo di runCont è

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

Il che allinea bene con il tipo della nostra >>==

Ora per rispondere realmente alla domanda

Ora dopo aver digitato tutto questo ho riletto la domanda iniziale. Il PO ha chiesto per la "differenza": P

Credo che la differenza è CPS dà più controllo chiamante, dove, come di solito il >>= in una monade è completamente controllato dall'autore del monade.

Answer 2

Si potrebbe desiderare di avere uno sguardo a questo http: //blog.sigfpe. com / 2008/12 / madre-of-all-monads.html

Answer 3

Un documento interessante che esplora la questione è "imperativo programmazione funzionale", di Peyton Jones e Wadler.

E 'la carta che ha introdotto monadica IO, e ha paragoni con approcci alternativi, tra cui CPS.

Gli autori concludono:

Quindi monadi sono più potenti di continuazioni, ma solo a causa dei tipi! Non è chiaro se questo è solo un artefatto del sistema di tipo Hindley-Milner, o se i tipi stanno rivelando una differenza di fondamentale importanza (la nostra intuizione è il secondo -. Ma è solo un'intuizione)

Answer 4

Non c'è alcuna relazione, così la domanda rende circa come molto senso come chiedere circa la differenza tra il colore blu e Plutone.