Monaden können als Formen von Containern interpretiert werden:
Ich frage mich, wie Fortsetzungen in dieser Sichtweise als Formen von Verpackungen / Containern sinnvoll interpretiert werden. Danke!
Ich denke an Fortsetzungen als Programme mit Löchern in ihnen. Ich denke, dass ich diese Einsicht ursprünglich von Tekmos Blog gesammelt habe.
Tekmo BlogSieh dir diese kleine Fortsetzung an:
%Vor% Es ist ein Programm, das "ein Stück fehlt" - nämlich, was mit Char geschehen soll, das von getChar abgerufen wurde. Wir können es ausführen, indem wir das fehlende Stück mit etwas wie putChar füllen; Wenn Sie die Fortsetzung über runContT program putChar auswerten, erhalten Sie ein Zeichen und drucken es dann auf stdout.
Wenn Sie mit der Darstellung von Programmen durch abstrakte Syntaxbäume vertraut sind, kann die Containeranalogie intuitiv sein.
Um es deutlicher zu machen, können Sie eine kleine AST mit einem DoThing -Term aufbauen, der ein Loch darstellt, das gefüllt werden muss:
program' ist hoffentlich klarer ein Container; Um es auszuführen, müssen wir den AST auf ähnliche Weise verarbeiten wie jeden anderen rekursiven Container:
Die Auswertung von program' via eval program' putChar entspricht der Ausführung von program via runContT program putChar .
Der wahre Schlüssel zum Verständnis von Monaden ist, aufzuhören,
zu sagenEine Monade ist X
und stattdessen anfangen zu sagen
X ist eine Monade
Etwas ist eine Monade, wenn es eine bestimmte Struktur hat und gewissen Gesetzen gehorcht . Für die Programmierung in Haskell ist etwas ein Monad , wenn es die richtige Art und die richtigen Typen hat und den Monad Gesetzen .
Gabriel Gonzales weist darauf hin, dass die Monadengesetze "die verkappten Kategoriengesetze" sind . Wir können % verwenden co_de% , das wie folgt definiert ist, anstatt >=> .
Wenn wir das tun, werden die Monadengesetze zu den Kategoriengesetzen mit der Identität >>= und der assoziativen Zusammensetzung return .
In Ihren Beispielen diskutieren Sie bereits zwei verschiedene Dinge für eine Monade: eine Aggregation, die flacht und eine Aggregation, die verwischt. Anstatt zu sagen, dass Monade beides ist, werden wir sagen, dass beides Monaden sind. Um Intuition darüber zu entwickeln, was Monaden sind, sprechen wir über die größte Klasse von Dingen, die alle Monaden sind.
Die größten Klassen, die >=> s sind, sind Bäume mit Pfropfung und Vereinfachung. Diese Klasse ist so groß, dass jede Monad , die ich in Haskell kenne, ein Baum mit Pfropfung ist. Jedes dieser Monaden enthält ein Monad , das einen Baum konstruiert, der den Wert an den Blättern hält, und eine Bindung return , die zwei Dinge tut. Bindung ersetzt jedes Blatt durch einen neuen Baum, pfropft den neuen Baum auf den Baum, wo das Blatt war, und vereinfacht den resultierenden Baum. Die Beispiele, die Sie erwähnen, unterscheiden sich darin, wie sie den Baum vereinfachen. Welche Vereinfachungen erlaubt sind, richtet sich nach den >>= -Gesetzen.
Wenn wir einen einfachen Baum haben, der Werte an seinen Blättern hält, ist es eine Monade.
%Vor% Sein Monad erstellt ein einzelnes return . Hier ist Leaf :
Seine Bindung ersetzt Blätter mit ganzen Bäumen. Wir beginnen mit folgendem Baum:
%Vor% Und bind dies an return 1 . Wir ersetzen jedes Blatt durch den neu berechneten Baum.
Bei normalen Bäumen führt der Pfropfschritt zu keiner Vereinfachung. Nachdem wir überprüft haben, dass diese Operationen den Monadengesetzen entsprechen, können wir sagen:
Ein Baum mit Pfropfen und ohne Vereinfachung ist eine Monade
Listen, Taschen, Sets, \x -> Branch [x*2, x*2 + 1] und Maybe reduzieren alle Ebenen des resultierenden Baums auf eine einzige Ebene. Alles, was irgendwo auf den Baum gepfropft wird, endet in der gleichen Liste oder Tasche oder in Identity . Sets entfernen auch alle Duplikate aus dem resultierenden einlagigen Baum.
Wenn wir dies an Just binden, ersetzen wir jedes Blatt durch die neue Struktur
und dann glätten Sie die Zwischenschicht
%Vor%Das können wir sagen
Eine flatternde Aggregation ist ein Baum mit Pfropfung und Vereinfachung
Und nachdem wir die Monadengesetze überprüft haben, können wir das sagen.
Eine flatternde Aggregation ist eine Monade
\x -> [x*2, x*2 + 1] und Paare wie Reader e sind ein bisschen anders. Sie können nicht alle Ergebnisse in einer einzelnen Ebene abflachen oder können dies zumindest nicht sofort tun. Stattdessen schneiden sie Zweige, die nicht in die gleiche Richtung wie die Eltern verzweigen.
Wenn wir mit einem Paar beginnen
%Vor% Wenn wir dies an data Pair a = Pair a a binden, ersetzen wir jedes Blatt durch die neue Struktur
Wir schneiden die Zweige, die nicht in die gleiche Richtung abzweigten
%Vor%Und dann kann man das zusätzlich vereinfachen, indem man die Ebenen abflacht
%Vor% Wie Sie bereits erwähnt haben, verzweigt \x -> <x*2, x*2 + 1> eine Anzahl von Richtungen, die der Anzahl der möglichen Werte von Reader e a entspricht.
Das können wir sagen
Eine Ansammlung, die Pflaumen und flach macht, ist ein Baum mit Pfropfung und Vereinfachung
Und nachdem wir die Monadengesetze überprüft haben, können wir das sagen.
Eine Ansammlung, die Pflaumen und flach macht, ist eine Monade
Die continuation monad ist ein Baum, der eine Verzweigung für jede der möglichen Fortsetzungen hat. Wir werden die Terminologie übernehmen, die Philip JF für Fortsetzungen vorgeschlagen hat .Die continuation monad ist das ganze e . Die Fortsetzung ist die (a -> r) -> r Funktion, die als erstes Argument
Die Fortsetzungs-Monade hat eine Anzahl von Zweigen gleich a -> r , die Anzahl der möglichen Werte der Fortsetzung |r| ^ |a| . Jeder Zweig ist mit einer entsprechenden Funktion gekennzeichnet. Eine Fortsetzung hat immer den gleichen Wert in jedem Blatt , was wir gleich rechtfertigen werden. Wir werden den internen Knoten des Baumes auch Beschriftungen hinzufügen, eine Funktion a -> r , auf die ich später eingehen werde.
Wir verwenden den folgenden Datentyp, um eine Beispielstruktur auszugeben.
%Vor% Unser Beispielbaum wird für r -> r sein. Der Typ der Werte in der Baumstruktur, return A :: Cont Bool Tri , hat drei Konstruktoren, und das Ergebnis der Monaden für die Kontination, Tri , hat zwei Konstruktoren. Es gibt Bool mögliche Funktionen 2 ^ 3 = 8 , die jeweils einen Zweig des Baumes bilden.
"Der Weg zum Herzen einer Monade ist durch ihre Kleisli-Pfeile" . Kleisli Pfeile sind die Dinge, die Sie an das zweite Argument von Tri -> Bool weitergeben können; Sie haben den Typ >>= . Wir werden die Kleisli-Pfeile von a -> m b untersuchen, die den Typ Cont haben, oder, wenn wir durch den a -> Cont r b -Konstruktor schauen
Wir können die Kleislipfeile der contination monad Cont in zwei Teile zerlegen. Der erste Teil ist die Funktion, die entscheidet, was a -> (b -> r) -> r in die Fortsetzung b übernehmen soll. Das einzige, mit dem es arbeiten muss, ist das Argument b -> r , also muss es eine der Funktionen a sein. Der zweite Teil ist die Funktion, die die Ergebnisse kombiniert. Es kann das Argument g :: a -> b und das Ergebnis der Übergabe von a in die Fortsetzung sehen. Wir werden diese zweite Funktion g a nennen. Alle Funktionen vom Typ r :: a -> r -> r können in der Form
für einige a -> (b -> r) -> r und g :: a -> b .
Ebenso kann jede Fortsetzungs-Monade r :: a -> r -> r in der Form
für einige (a -> r) -> r und a :: a . Zusammengenommen bilden sie die Begründung, dass eine Fortsetzungs-Monade in jedem Blatt immer den gleichen Wert hat.
Wenn wir eine Funktion r :: r -> r an einen Continuation Monad Tree binden, zeichnen wir \x -> \f -> r x (f (g x)) als neue Blätter auf und zeichnen g x als Label für den neuen Zwischenknoten auf. Die Bäume sind wirklich groß, aber wir werden die Ecke eines anderen vollständigen Beispiels mit (r x, g x) zeichnen, wobei \x -> \f -> r x (f (g x)) :: Tri -> (Bit -> Bool) -> Bool nur zwei Konstruktoren hat. Die resultierende Continuation Monade sollte nur Bit Zweige haben, aber wir haben es noch nicht vereinfacht.
Da jedes Blatt denselben Wert hat, sind die einzigen Unterschiede zwischen den Pfaden durch den Baum die Funktionen, die jeden Zweig bezeichnen. Wir werden die Etiketten aus den Filialen entfernen und nur einen Zweig zeichnen. Unser erstes Beispiel für |Bool| ^ |Bit| = 4 wird nun als
Und das Beispiel der Bindung von return a an \x -> \f -> r x (f (g x)) wird als
Jede Fortsetzungs-Monade, die in der Form return A für einige \f -> r (f a) und a :: a geschrieben ist, wird durch die Struktur
Wenn es an r :: r -> r gebunden ist, wird es durch den folgenden Baum dargestellt (dies ist nur Pfropfen)
Wir werden herausfinden, was der Vereinfachungsschritt von Definition von \x -> \f' -> r' x (f' (g' x)) für >>= .
in der Form Cont . Unser Baum wird zu
Die Fortsetzungs-Monade ist ein Baum, dessen interne Knoten mit Funktionen beschriftet sind. Seine Bindeoperation ist eine Baumtransplantation gefolgt von einem Vereinfachungsschritt. Der Vereinfachungsschritt setzt die Funktionen auf den internen Knoten zusammen. Das können wir sagen.
Die Fortsetzungs-Monade ist ein Baum mit Pfropfung und Vereinfachung
Und nachdem wir die Monadengesetze überprüft haben, können wir das sagen.
Die Fortsetzungs-Monade ist eine Monade
Tags und Links haskell continuations monads