Habe versucht, den Z-Kombinator abzuleiten und habe stattdessen einen anderen abgeleitet

Question

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?

Answer 1

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)))