Ho cercato di ricavare il combinatore Z e invece ne deriva un altro

Question

Stavo lavorando per derivare il combinatore Z iniziando con la funzione fattoriale e ha finito per derivare un diverso combinatore di punti fissi. Cosa ho ricavato? Ho fatto un errore sottile?

Ecco i passaggi che ho eseguito (in JavaScript)

1. Dichiarare la funzione fattoriale

let fact = n =>
    n < 2 ? 1 : n * fact(n - 1)

.

2. Converti in combinatore (espressione chiusa)

let fact = (self, n) =>
    n < 2 ? 1 : n * self(n - 1)

.

3. Thread Liquid

Sulla base della firma fact(?, 7), passando fact come primo argomento sembra un aspetto genernicodetagCode ragionevole. Quindi thread il parametro attraverso la chiamata di coda:

let fact = (self, n) =>
    n < 2 ? 1 : n * self(self, n - 1)

.

L'utilizzo è ora fact(fact,7) → fact(fact,7)

4. Rifactor a forma di curry

let fact = self =>
    n => n < 2 ? 1 : n * self(self)(n - 1)

.

5. Sposta l'applicazione auto alla Dichiarazione locale

let fact = self => {
    let f = n => self(self)(n)
    return n => n < 2 ? 1 : n * f(n - 1)
}

.

6. Converti Converti Dichiarazione all'espressione Lambda

let fact = self =>
    (f =>
        n => n < 2 ? 1 : n * f(n - 1)
    )(
        n => self(self)(n)
    )

.

L'utilizzo è ancora 5040 → fact(fact)(7)

7. Separare l'espressione fattoriale

let _fact = f => n =>
    n < 2 ? 1 : n * f(n - 1)

let fact = self =>
    (
        _fact
    )(
        n => self(self)(n)
    )

.

8. Sposta l'auto-applicazione dal chiamante al corpo

let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    let innerFact = self =>
        (
            _fact
        )(
            n => self(self)(n)
        )
    return innerFact(innerFact)
})()

.

L'utilizzo è ora 5040 → fact(7)

9. Converti Converti Dichiarazione all'espressione Lambda

let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact = (() => {
    return (
        innerFact => innerFact(innerFact)
    )(
        self => (_fact)(n => self(self)(n))
    )
})()

.

10. Semplificare l'espressione

let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (innerFact => innerFact(innerFact))
    (self => (_fact)(n => self(self)(n)))

.

Controllo sanitario. L'utilizzo è ancora 5040 → fact(7)

11. Rinomina variabili

L'utilizzo di 5040 e innerFact sembra sospettosamente simile. Rinominare alla stessa variabile per scoprire un modello. Scopa lessicali separati così sicuri da fare:

let _fact =
    f => n => n < 2 ? 1 : n * f(n - 1)

let fact =
    (u => u(u))
    (u => (_fact)(n => u(u)(n)))

.

12. Abstract self Uso e rinomina _fact

Rinomina fact a fact e setup astratto nel corpo Sostituendo con il parametro _fact

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)

.

Non c'è bisogno di Dichiarazione di f separato così in linea:

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. Rinomina _fact

Rinominalo a cosa? Che combinatore è questo? Secondo wikipedia il combinatore Z è:

let Z = f => 
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

.

Ma quello che ho derivato è:

let setup = f =>
    (u => u(u))
    (u => (f)(n => u(u)(n)))

.

Definizione del setup in termini di sembra equivalente nel comportamento. Ho fatto un errore? Ho riscoperto accidentalmente un altro ben noto combinatore?

Answer 1

Se I Inline (u => (f)(n => u(u)(n))) in (u => u(u)) Io ottengo:

(u => f(n => u(u)(n)))
(u => f(n => u(u)(n)))

.

che è esattamente il combinatore Z.

Da Wikipedia:

let Z = f => 
    (u => f(v => u(u)(v)))
    (u => f(v => u(u)(v)))

.

La mia derivazione:

let fix = f =>
    (u => f(n => u(u)(n)))
    (u => f(n => u(u)(n)))

.