Habe versucht, den Z-Kombinator abzuleiten und habe stattdessen einen anderen abgeleitet
-
29-09-2020 - |
Frage
Ich habe daran gearbeitet, den Z-Kombinator abzuleiten, indem ich mit der Fakultätsfunktion begonnen habe, und habe schließlich einen anderen Festkomma-Kombinator abgeleitet.Was habe ich abgeleitet?Habe ich einen subtilen Fehler gemacht?
Hier sind die Schritte, die ich ausgeführt habe (in JavaScript)
1.Fakultätsfunktion deklarieren
let fact = n =>
n < 2 ? 1 : n * fact(n - 1)
2.In Kombinator umwandeln (geschlossener Ausdruck)
let fact = (self, n) =>
n < 2 ? 1 : n * self(n - 1)
3.Thread-Selbstaufruf
Basierend auf der Unterschrift fact(?, 7)
, Vorbeigehen fact
als erstes Argument erscheint vernünftig fact(fact,7)
.Führen Sie den Parameter also durch den Tail-Call:
let fact = (self, n) =>
n < 2 ? 1 : n * self(self, n - 1)
Die Nutzung ist jetzt fact(fact,7)
→ 5040
4.Umgestaltung in Curry-Form
let fact = self =>
n => n < 2 ? 1 : n * self(self)(n - 1)
5.Eigenanwendung in lokale Deklaration verschieben
let fact = self => {
let f = n => self(self)(n)
return n => n < 2 ? 1 : n * f(n - 1)
}
6.Konvertieren Sie die Let-Deklaration in einen Lambda-Ausdruck
let fact = self =>
(f =>
n => n < 2 ? 1 : n * f(n - 1)
)(
n => self(self)(n)
)
Die Nutzung erfolgt weiterhin fact(fact)(7)
→ 5040
7.Trennen Sie den faktoriellen Ausdruck
let _fact = f => n =>
n < 2 ? 1 : n * f(n - 1)
let fact = self =>
(
_fact
)(
n => self(self)(n)
)
8.Verschieben Sie die Selbstanwendung vom Anrufer zum Körper
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let fact = (() => {
let innerFact = self =>
(
_fact
)(
n => self(self)(n)
)
return innerFact(innerFact)
})()
Die Nutzung ist jetzt fact(7)
→ 5040
9.Konvertieren Sie die Let-Deklaration in einen Lambda-Ausdruck
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let fact = (() => {
return (
innerFact => innerFact(innerFact)
)(
self => (_fact)(n => self(self)(n))
)
})()
10.Ausdruck vereinfachen
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let fact =
(innerFact => innerFact(innerFact))
(self => (_fact)(n => self(self)(n)))
Gesundheitsüberprüfung.Die Nutzung erfolgt weiterhin fact(7)
→ 5040
11.Variablen umbenennen
Die Verwendung von innerFact
Und self
sehen verdächtig ähnlich aus.Benennen Sie sie in dieselbe Variable um, um ein Muster zu erkennen.So sicher können Sie lexikalische Bereiche trennen:
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let fact =
(u => u(u))
(u => (_fact)(n => u(u)(n)))
12.Abstrakt _fact
Verwendung und Umbenennen fact
Umbenennen fact
Zu setup
und abstrakt _fact
im Körper durch Ersetzen durch Parameter f
let _fact =
f => n => n < 2 ? 1 : n * f(n - 1)
let setup = f =>
(u => u(u))
(u => (f)(n => u(u)(n)))
let fact = setup(_fact)
Keine separate Notwendigkeit _fact
Deklaration also inline:
let setup = f =>
(u => u(u))
(u => (f)(n => u(u)(n)))
let fact = setup(
f => n => n < 2 ? 1 : n * f(n - 1)
)
13.Umbenennen setup
Umbenennen in was?Welcher Kombinator ist das?Entsprechend Wikipedia Der Z-Kombinator ist:
let Z = f =>
(u => f(v => u(u)(v)))
(u => f(v => u(u)(v)))
Aber was ich abgeleitet habe, ist:
let setup = f =>
(u => u(u))
(u => (f)(n => u(u)(n)))
Definieren fact
in Bezug auf beides scheint das Verhalten gleichwertig zu sein.Habe ich einen Fehler gemacht?Habe ich versehentlich einen anderen bekannten Kombinator wiederentdeckt?
Lösung
Wenn ich inline bin (u => (f)(n => u(u)(n)))
hinein (u => u(u))
Ich bekomme:
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))
Das ist genau der Z-Combinator.
Aus Wikipedia:
let Z = f =>
(u => f(v => u(u)(v)))
(u => f(v => u(u)(v)))
Meine Ableitung:
let fix = f =>
(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))