Wie und warum funktioniert die Haskell Cont-Monade?

So wird die Cont-Monade definiert:

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

Können Sie erklären, wie und warum dies funktioniert? Was macht es?

Das Erste, was man an der Fortsetzungsmonade erkennen muss, ist, dass sie im Grunde genommen überhaupt nichts tut . Das ist wahr!

Die Grundidee einer Fortsetzung im Allgemeinen ist, dass sie den Rest einer Berechnung darstellt . Angenommen, wir haben einen Ausdruck wie diesen : foo (bar x y) z. Extrahieren Sie nun nur den in Klammern bar x ygesetzten Teil. Dies ist Teil des Gesamtausdrucks, aber nicht nur eine Funktion, die wir anwenden können. Stattdessen müssen sie etwas , das wir eine Funktion anwenden zu . Wir können also in diesem Fall vom "Rest der Berechnung" sprechen \a -> foo a z, auf den wir uns beziehen können, bar x yum die vollständige Form zu rekonstruieren.

Nun kommt es vor, dass dieses Konzept des "Restes der Berechnung" nützlich ist, aber es ist umständlich, damit zu arbeiten, da es etwas außerhalb des von uns in Betracht gezogenen Unterausdrucks ist. Damit die Dinge besser funktionieren, können wir die Dinge auf den Kopf stellen: Extrahieren Sie den Unterausdruck, an dem wir interessiert sind, und wickeln Sie ihn in eine Funktion ein, die ein Argument enthält, das den Rest der Berechnung darstellt : \k -> k (bar x y).

Diese modifizierte Version bietet uns viel Flexibilität - sie extrahiert nicht nur einen Unterausdruck aus ihrem Kontext, sondern ermöglicht es uns auch , diesen äußeren Kontext innerhalb des Unterausdrucks selbst zu manipulieren . Wir können es uns als eine Art suspendierte Berechnung vorstellen , die uns explizite Kontrolle darüber gibt, was als nächstes passiert. Wie können wir das verallgemeinern? Nun, der Unterausdruck ist so gut wie unverändert. Ersetzen wir ihn also einfach durch einen Parameter für die Inside-Out-Funktion und geben uns \x k -> k x- mit anderen Worten, nichts weiter als eine umgekehrte Funktionsanwendung . Wir könnten genauso gut schreiben flip ($)oder ein bisschen exotische Fremdsprache hinzufügen und es als Operator definieren |>.

Nun wäre es einfach, wenn auch mühsam und schrecklich verschleiert, jedes Stück eines Ausdrucks in diese Form zu übersetzen. Zum Glück gibt es einen besseren Weg. Wenn wir als Haskell-Programmierer denken, dass das Erstellen einer Berechnung in einem Hintergrundkontext das nächste ist, was wir denken , ist dies eine Monade? Und in diesem Fall lautet die Antwort ja , ja, das ist es.

Um daraus eine Monade zu machen, beginnen wir mit zwei Grundbausteinen:

• Für eine Monade msteht ein Wert vom Typ m afür den Zugriff auf einen Wert vom Typ aim Kontext der Monade.
• Der Kern unserer "suspendierten Berechnungen" ist die gespiegelte Funktionsanwendung.

Was bedeutet es, in adiesem Zusammenhang Zugang zu etwas Typischem zu haben ? Es bedeutet nur , dass, für einen Wert x :: ahaben wir angewandt flip ($)auf x, uns eine Funktion geben , die eine Funktion übernimmt , die ein Argument vom Typ nimmt a, und wendet diese Funktion x. Angenommen, wir haben eine angehaltene Berechnung, die einen Wert vom Typ enthält Bool. Welchen Typ gibt uns das?

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

Für suspendierte Berechnungen m afunktioniert der Typ also mit (a -> b) -> b... was vielleicht ein Höhepunkt ist, da wir die Signatur für bereits kannten Cont, aber mich vorerst humorisieren .

Interessant ist hier, dass eine Art "Umkehrung" auch für den Typ der Monade gilt: Cont b astellt eine Funktion dar, die eine Funktion übernimmt a -> bund auswertet b. Da eine Fortsetzung "die Zukunft" einer Berechnung darstellt, arepräsentiert der Typ in der Signatur in gewissem Sinne "die Vergangenheit".

Also, ersetzt (a -> b) -> bmit Cont b a, was ist der monadischen Typ für unsere Grundbaustein der Reverse - Funktion Anwendung? a -> (a -> b) -> bübersetzt zu a -> Cont b a... der gleichen Typensignatur wie returnund tatsächlich ist es genau das, was es ist.

Von hier an fällt alles ziemlich direkt aus den Typen heraus: Es gibt im Grunde keinen vernünftigen Weg, um >>=außer der tatsächlichen Implementierung zu implementieren. Aber was ist es eigentlich zu tun ?

An dieser Stelle kommen wir zurück zu dem, was ich sagte zu Beginn: die Fortsetzung Monade ist nicht wirklich tut so gut wie nichts. Etwas vom Typ Cont r aist trivial äquivalent zu etwas vom gerechten Typ a, indem einfach idals Argument für die angehaltene Berechnung angegeben wird. Dies könnte dazu führen, dass man sich fragt, ob, wenn Cont r aes sich um eine Monade handelt, die Bekehrung aber so trivial ist, nicht aallein auch eine Monade sein sollte. Das funktioniert natürlich nicht so wie es ist, da es keinen Typkonstruktor gibt, der als MonadInstanz definiert werden kann, aber sagen wir, wir fügen einen trivialen Wrapper hinzu, wie z data Id a = Id a. Dies ist in der Tat eine Monade, nämlich die Identitätsmonade.

Was macht >>=die Identitätsmonade? Die Typensignatur ist Id a -> (a -> Id b) -> Id bäquivalent zu a -> (a -> b) -> b, was wiederum nur eine einfache Funktionsanwendung ist. Nachdem wir festgestellt haben, dass dies Cont r atrivial äquivalent zu ist Id a, können wir daraus schließen, dass es sich auch in diesem Fall (>>=)nur um eine Funktionsanwendung handelt .

Natürlich Cont r aist es eine verrückte umgekehrte Welt, in der jeder Ziegenbart hat. Was also tatsächlich passiert, ist, die Dinge auf verwirrende Weise durcheinander zu bringen, um zwei suspendierte Berechnungen zu einer neuen suspendierten Berechnung zusammenzufassen, aber im Wesentlichen gibt es eigentlich nichts Ungewöhnliches auf! Funktionen auf Argumente anwenden, ho hum, ein weiterer Tag im Leben eines funktionierenden Programmierers.

Hier ist Fibonacci:

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

Stellen Sie sich vor, Sie haben eine Maschine ohne Aufrufstapel - sie ermöglicht nur die Schwanzrekursion. Wie fibauf diesem Computer ausführen ? Sie können die Funktion leicht umschreiben, um in linearer statt in exponentieller Zeit zu arbeiten, aber das erfordert ein wenig Einsicht und ist nicht mechanisch.

Das Hindernis, um den Schwanz rekursiv zu machen, ist die dritte Zeile, in der es zwei rekursive Aufrufe gibt. Wir können nur einen einzigen Anruf tätigen, der auch das Ergebnis liefern muss. Hier kommen Fortsetzungen ins Spiel.

Wir werden einen fib (n-1)zusätzlichen Parameter nehmen, der eine Funktion ist, die angibt, was nach der Berechnung des Ergebnisses zu tun ist, und ihn aufrufen x. Es wird fib (n-2)natürlich dazu beitragen. Also: berechnen fib nSie berechnen fib (n-1)danach, wenn Sie das Ergebnis nennen x, berechnen Sie fib (n-2), danach, wenn Sie das Ergebnis nennen y, Sie zurückkommen x+y.

Mit anderen Worten muss man sagen:

Wie wird die folgende Berechnung durchgeführt: " fib' n c= Berechnen fib nund cauf das Ergebnis anwenden "?

Die Antwort lautet, dass Sie Folgendes tun: "Berechnen fib (n-1)und dauf das Ergebnis anwenden ", wobei d x"Berechnen fib (n-2)und eauf das Ergebnis anwenden " e ybedeutet , wobei " bedeutet" c (x+y). In Code:

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)

Gleichermaßen können wir Lambdas verwenden:

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

Um tatsächliche Fibonacci zu erhalten, verwenden Sie Identität : fib' n id. Sie können sich vorstellen, dass die Zeile fib (n-1) $ ...ihr Ergebnis xan die nächste weitergibt.

Die letzten drei Zeilen riechen dotatsächlich nach einem Block

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

ist bis auf neue Typen per Definition der Monade gleich Cont. Unterschiede beachten. Es gibt \c ->am Anfang, statt x <- ...gibt ... $ \x ->und cstatt return.

Versuchen Sie, factorial n = n * factorial (n-1)mit CPS in einem rekursiven Schwanzstil zu schreiben .

Wie funktioniert das >>=? m >>= kist äquivalent zu

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

Wenn Sie die Übersetzung im gleichen Stil wie in fib'zurücksetzen, erhalten Sie

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

Vereinfachung \t -> c tzuc

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

Hinzufügen neuer Typen, die Sie erhalten

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

Das ist oben auf dieser Seite. Es ist komplex, aber wenn Sie wissen, wie man zwischen doNotation und direkter Verwendung übersetzt, müssen Sie die genaue Definition von nicht kennen >>=! Die Fortsetzungsmonade ist viel klarer, wenn Sie sich Do-Blöcke ansehen.

Monaden und Fortsetzungen

Wenn Sie sich diese Verwendung von Listenmonade ansehen ...

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)

das sieht nach Fortsetzung aus! In der Tat, (>>=)wenn Sie ein Argument anwenden, hat Typ, (a -> m b) -> m bder ist Cont (m b) a. Siehe sigfpes Mutter aller Monaden zur Erklärung. Ich würde das als eine gute Fortsetzung Monad Tutorial betrachten, obwohl es wahrscheinlich nicht so gemeint war.

Da Fortsetzungen und Monaden in beiden Richtungen so stark miteinander verbunden sind, denke ich, dass das, was für Monaden gilt, für Fortsetzungen gilt: Nur harte Arbeit wird sie lehren und keine Burrito-Metapher oder Analogie lesen.

BEARBEITEN: Artikel auf den unten stehenden Link migriert.

Ich habe ein Tutorial geschrieben, das sich direkt mit diesem Thema befasst und das Sie hoffentlich nützlich finden werden. (Es hat sicherlich dazu beigetragen, mein Verständnis zu festigen!) Es ist etwas zu lang, um bequem in ein Stapelüberlauf-Thema zu passen, also habe ich es in das Haskell-Wiki migriert.

Bitte sehen Sie: MonadCont unter der Haube

Ich denke, der einfachste Weg, die ContMonade in den Griff zu bekommen, besteht darin, zu verstehen, wie man ihren Konstruktor benutzt. Ich gehe vorerst von der folgenden Definition aus, obwohl die Realitäten des transformersPakets etwas anders sind:

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

Das gibt:

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

Cont r aUm einen Wert vom Typ Typ zu erstellen , müssen wir eine Funktion zuweisen für Cont:

value = Cont $ \k -> ...

Jetzt hat es kselbst Typ a -> r, und der Körper des Lambda muss Typ haben r. Eine naheliegende Sache wäre, kauf einen Wert vom Typ anzuwenden aund einen Wert vom Typ zu erhalten r. Wir können das tun, ja, aber das ist wirklich nur eines von vielen Dingen, die wir tun können. Denken Sie daran, valuedass es nicht polymorph sein muss r, sondern vom Typ Cont String Integeroder etwas anderem Konkretes sein kann. Damit:

• Wir könnten kauf mehrere Werte des Typs anwenden aund die Ergebnisse irgendwie kombinieren.
• Wir könnten kauf einen Wert vom Typ anwenden a, das Ergebnis beobachten und uns dann entscheiden, kauf etwas anderes basierend darauf anzuwenden .
• Wir könnten alles ignorieren kund selbst einen rTypwert produzieren.

Aber was bedeutet das alles? Was ist am kEnde? Nun, in einem Do-Block könnten wir so etwas haben:

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

Hier ist der lustige Teil: Wir können in unseren Gedanken und etwas informell den do-Block beim Auftreten des ContKonstruktors in zwei Teile teilen und den Rest der gesamten Berechnung danach als einen Wert an sich betrachten. Aber Moment xmal , was es ist, hängt davon ab, was es ist. Es ist also wirklich eine Funktion von einem Wert xvom Typ abis zu einem Ergebniswert:

restOfTheComputation x = do
  thing3 x
  thing4

In der Tat, dies restOfTheComputationist grob gesagt , was koben ist , endet. Mit anderen Worten, Sie rufen kmit einem Wert auf, der das Ergebnis xIhrer ContBerechnung wird, der Rest der Berechnung wird ausgeführt, und dann rerzeugt sich das erzeugte Ergebnis als Ergebnis des Aufrufs an in Ihr Lambda zurück k. Damit:

• Wenn Sie kmehrmals aufgerufen haben, wird der Rest der Berechnung mehrmals ausgeführt, und die Ergebnisse können beliebig kombiniert werden.
• Wenn Sie überhaupt nicht aufgerufen haben k, wird der Rest der gesamten Berechnung übersprungen, und der beiliegende runContAufruf gibt Ihnen nur den Wert des Typs zurück, den rSie synthetisiert haben. Das heißt, es sei denn , ein anderer Teil der Berechnung ruft man von ihr k , und Flickschusterei mit dem Ergebnis ...

Wenn Sie zu diesem Zeitpunkt noch bei mir sind, sollte es leicht zu erkennen sein, dass dies ziemlich mächtig sein könnte. Lassen Sie uns einige Standardtypklassen implementieren, um den Punkt ein wenig zu verdeutlichen.

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

Wir erhalten einen ContWert mit dem Bindungsergebnis xvom Typ aund eine Funktion f :: a -> b, und wir möchten einen ContWert mit dem Bindungsergebnis f xvom Typ erstellen b. Um das Bindungsergebnis festzulegen, rufen Sie einfach k...

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

Warten Sie, woher kommen wir x? Nun, es wird involviert sein c, was wir noch nicht benutzt haben. Denken cSie daran, wie es funktioniert: Es erhält eine Funktion und ruft diese Funktion mit ihrem Bindungsergebnis auf. Wir wollen unsere Funktion mit fauf dieses Bindungsergebnis angewendet aufrufen . Damit:

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

Tada! Als nächstes Applicative:

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

Das ist einfach. Wir möchten, dass das Bindungsergebnis das ist, das xwir erhalten.

  pure x = Cont $ \k -> k x

Nun <*>:

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

Dies ist etwas kniffliger, verwendet jedoch im Wesentlichen dieselben Ideen wie in fmap: Holen Sie sich zuerst die Funktion von Anfang an Cont, indem Sie ein Lambda erstellen , damit es Folgendes aufruft :

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

Holen Sie sich dann den Wert xaus der Sekunde und erstellen Sie fn xdas Bindungsergebnis:

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

Monadist ähnlich, obwohl erfordert runContoder ein Fall oder lassen Sie den Newtype entpacken.

Diese Antwort ist schon ziemlich lang, also werde ich nicht darauf eingehen ContT(kurz: es ist genau das gleiche wie Cont! Der einzige Unterschied besteht in der Art des Typkonstruktors, die Implementierungen von allem sind identisch) oder callCC(ein nützlicher Kombinator, der bietet eine bequeme Möglichkeit zum Ignorieren kund Implementieren eines frühen Austritts aus einem Unterblock.

Versuchen Sie für eine einfache und plausible Anwendung den Blog-Beitrag von Edward Z. Yang, in dem die Bezeichnung break implementiert ist , und fahren Sie mit den Schleifen fort .

Der Versuch, die anderen Antworten zu ergänzen:

Verschachtelte Lambdas sind für die Lesbarkeit schrecklich. Dies ist genau der Grund, warum ... in ... und ... wo ... existieren, um verschachtelte Lambdas mithilfe von Zwischenvariablen zu entfernen. Mit diesen kann die Bindungsimplementierung in Folgendes umgestaltet werden:

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

instance Monad (Cont r) where
    return a = Cont ($ a)
    m >>= k  = k a
            where a = runCont m id

Was hoffentlich klarer macht, was passiert. Der Wert für die Rückgabeimplementierungsfelder ist faul. Wenn Sie die runCont-ID verwenden, wird die ID auf den Boxwert angewendet, der den ursprünglichen Wert zurückgibt.

Für jede Monade, bei der ein Boxwert einfach entpackt werden kann, gibt es im Allgemeinen eine triviale Implementierung von bind, bei der der Wert einfach entpackt und eine monadische Funktion darauf angewendet wird.

Um die verschleierte Implementierung in der ursprünglichen Frage zu erhalten, ersetzen Sie zuerst ka durch Cont $ runCont (ka), das wiederum durch Cont $ \ c-> runCont (ka) c ersetzt werden kann

Jetzt können wir das Wo in einen Unterausdruck verschieben, so dass wir übrig bleiben

Cont $ \c-> ( runCont (k a) c where a = runCont m id )

Der Ausdruck in Klammern kann in \ a -> runCont (ka) c $ runCont m id desugariert werden.

Zum Abschluss verwenden wir die Eigenschaft von runCont, f (runCont mg) = runCont m (fg), und kehren zum ursprünglichen verschleierten Ausdruck zurück.