Ich versuche, eine stack -Datenstruktur im Lambda-Kalkül zu definieren, indem ich Festkomma-Kombinatoren verwende. Ich versuche, zwei Operationen zu definieren, insertion und removal der Elemente, also, push und pop , aber die einzige, die ich definieren konnte, die Einfügung, funktioniert nicht richtig. Die Entfernung konnte ich nicht herausfinden, wie zu definieren.
Dies ist mein Ansatz für die Operation push und meine Definition für stack :
Meine Stapel werden mit einem Element initialisiert, um den Boden anzuzeigen; Ich verwende hier ein 0 :
Aber jetzt, wenn ich versuche, ein anderes Element einzufügen, funktioniert es nicht, da meine ursprüngliche Struktur dekonstruiert wurde.
Wie behebe ich die Definition von STACK oder PUSH und wie definiere ich die Operation POP ? Ich denke, ich muss einen Kombinator anwenden, um Rekursion zu ermöglichen, aber ich konnte nicht herausfinden, wie es geht.
Referenz: Ссылка
Jede weitere Erklärung oder ein Beispiel zur Definition einer Datenstruktur im Lambda-Kalkül wird sehr geschätzt.
Ein Stapel im Lambda-Kalkül ist nur eine einfach verknüpfte Liste. Und eine einfach verknüpfte Liste gibt es in zwei Formen:
%Vor% Dies ist Church encoding , mit einer Liste als Katamorphose . Wichtig ist, dass Sie keinen Fixpunktkombinator benötigen. In dieser Ansicht ist ein Stack (oder eine Liste) eine Funktion, die ein Argument für die nil -Klasse und ein Argument für die cons -Klasse verwendet. Zum Beispiel wird die Liste [a,b,c] wie folgt dargestellt:
Der leere Stapel nil entspricht dem K -Kombinator des SKI-Kalküls. Der cons -Konstruktor ist Ihre Operation push . Wenn ein Kopfelement h und ein weiterer Stapel t für den Schwanz angegeben wird, ist das Ergebnis ein neuer Stapel mit dem Element h an der Vorderseite.
Die Operation pop trennt die Liste einfach in Kopf und Schwanz. Sie können dies mit einem Paar Funktionen tun:
Wo e etwas ist, das den leeren Stapel handhabt, da das Aufheben des leeren Stapels nicht definiert ist. Diese können leicht in eine Funktion umgewandelt werden, die das Paar head und tail zurückgibt:
Auch hier ist das Paar in der Kirche kodiert. Ein Paar ist nur eine Funktion höherer Ordnung. Das Paar (a, b) wird als Funktion höherer Ordnung λf. f a b dargestellt. Es ist nur eine Funktion, die bei einer anderen Funktion f f auf a und b anwendet.
Durch Definieren eines Kombinators, der:
ist definiert als ein Lambda-Ausdruck ohne freie Variablen, daher ist per Definition jeder Kombinator bereits ein Lambda-Ausdruck,
Sie können zum Beispiel eine Listenstruktur definieren, indem Sie schreiben:
%Vor%Intuitiv und unter Verwendung eines Fixpunktkombinators ist eine mögliche Definition - betrachte \ = lambda:
0 ; x gebildet, das eine andere Liste innerhalb der vorherigen sein kann. Da es mit einem Kombinator - einem Fixpunktkombinator - definiert wurde, müssen keine weiteren Anwendungen mehr ausgeführt werden. Die folgende Abstraktion ist ein Lambda-Ausdruck selbst.
%Vor%Nun benenne ich es als LIST:
%Vor% Der Festkomma-Kombinator Y , oder einfach Kombinator, erlaubt es Ihnen, die Definition von LIST bereits als gültiges Mitglied zu betrachten, ohne freie Variablen, also ohne Reduzierungen.
Dann können Sie Elemente wie 1 und 2 anfügen / einfügen, indem Sie:
%Vor%Aber hier kennen wir die Definition der Liste, also erweitern wir sie:
%Vor% Nun, elemenet 2 einfügen:
Dies kann im Falle einer neuen Einfügung erweitert werden oder einfach so belassen werden, weil LIST ein Lambda-Ausdruck ist, der mit einem Kombinator definiert ist.
Erweiterung für zukünftige Einfügungen:
%Vor%Ich bin wirklich froh, dass ich das selbst herausfinden konnte, aber ich bin mir ziemlich sicher, dass es einige gute zusätzliche Bedingungen geben muss, wenn man einen Stapel, einen Haufen oder eine feinere Struktur definiert.
>Der Versuch, die Abstraktion für einen Stack-Ein- / Ausbau abzuleiten - ohne all den Schritt-für-Schritt:
%Vor%Um die Operation auszuführen, nennen wir einen leeren Stack - eine Variable zuweisen (:
%Vor%Und wir nennen dieses Ergebnis noch einmal, damit wir die Elemente knacken können:
%Vor% Dafür haben wir hoffentlich das Element 3 gepoppt.
Ich habe versucht, dies selbst abzuleiten, also, wenn es irgendeine Einschränkung aus dem Lambda-Kalkül gibt, der ich nicht gefolgt bin, bitte, weisen Sie darauf hin.
Tags und Links lambda functional-programming lambda-calculus combinators y-combinator