Fortsetzung Übertragungsstil vs Monaden

Question

Was sind die Unterschiede zwischen Fortsetzungs sind vorbei Stil (cps) und Monaden.

Answer 1

Wie bereits erwähnt in Das Wesen der funktionalen Programmierung :

Programmierung mit Monaden erinnert stark an Weiter-Passing-Stil (CPS), und dieses Papier untersucht die Beziehung zwischen den beiden. In gewissem Sinne sind sie äquivalent: CPS stellt sich als Spezialfall einen monadisch und jeder monadisch kann durch Ändern des Antworttypen in CPS eingebettet werden. Aber der monadischen Ansatz bietet zusätzliche Einblicke und ermöglicht eine feinere Kontrolle geraten.

Das Papier ist ziemlich streng, und eigentlich ist es nicht ganz erweitert auf die Beziehung zwischen CPS und Monaden. Hier versuche ich, ein informelles, aber anschauliches Beispiel zu geben:

. (Anmerkung: Im Folgenden finden Sie ein Verständnis von Monade von einem Neuling (ich), obwohl nach dem Schreiben sieht es scheint wie eine dieser High-rep Benutzer Antwort Bitte nehmen Sie es mit einer Tonne Salz)

Betrachten wir die klassische 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

So stoppt die Berechnung sobald Nothing angetroffen wird, nichts Neues. Lassen Sie uns versuchen zu imitieren so ein monadischen Verhalten unter Verwendung von CPS:

Hier ist unsere Vanille add Funktion CPS verwenden. Wir verwenden alle Int hier statt algebraischen Datentyp es einfacher zu machen:

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

GHCi> add 3 4 id
7

Beachten Sie, wie ähnlich es ist eine Monade

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

GHCi> foo
12

OK. Nehmen wir an, dass wir die Berechnung soll bei 10 werden gekappt Das heißt, was auch immer Berechnung muss aufhören, wenn der nächste Schritt in einem Wert führen würde, größer als 10. Dies ist eine Art wie wenn man sagt „a Vielleicht Berechnung muss aufhören und Rückkehr Nothing sobald jeder Wert in der Kette ist Nothing). Mal sehen, wie wir es durch das Schreiben eines „CPS-Transformator“ tun können,

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

Beachten Sie, dass die Endwert Rückkehr kann undefined sein, aber das ist in Ordnung, weil die Auswertung auf dem 3. Schritt hält (z).

Wir können sehen, dass cap10 „Wraps“ die normale Fortsetzung mit einigen zusätzlichen Logik. Und das ist ganz in der Nähe, was Monade -. Klebstoff Berechnungen zusammen mit einigen zusätzlichen Logik

Lassen Sie uns gehen noch einen Schritt weiter:

(>>==) :: ((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! Vielleicht haben wir gerade die Cap10 Monade erfunden!

Nun, wenn wir uns den Quellcode Cont sehen wir, dass Cont ist

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

Die Art der runCont ist

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

Welche Linien schön mit der Art unserer >>==

Nun

, um tatsächlich die Frage zu beantworten

Nun, nachdem alle diese Eingabe Ich las die ursprüngliche Frage. Die OP fragte nach der "Differenz": P

ich denke, der Unterschied ist CPS den Anrufer mehr Kontrolle gibt, wo, wie in der Regel die >>= in einer Monade vollständig durch die Monade des Autors gesteuert wird.

Answer 2

Sie können einen Blick auf diese http haben wollen: //blog.sigfpe. com / 2008/12 / Mutter-of-all-monads.html

Answer 3

Ein interessantes Papier, das die Frage untersucht, ist "Imperative funktionale Programmierung" , von Peyton Jones und Wadler.

Es ist das Papier, das monadische IO eingeführt, und es hat Vergleiche zu alternativen Ansätzen, einschließlich CPS.

Die Autoren folgern:

So Monaden ist mächtiger als Fortsetzungen, aber nur wegen der Art! Es ist nicht klar, ob dies nur ein Artefakt des Hindley-Milner-Typ-Systems ist, oder ob die Typen einen Unterschied von grundlegender Bedeutung sind aufschlussreich (eigene Intuition ist es das letzteres -. Aber es ist nur eine Intuition)

Answer 4

Es gibt keine Beziehung, also die Frage, macht ungefähr so ??viel Sinn wie zwischen der Farbe Blau und Pluto über den Unterschied zu fragen.