Essayé de tirer le Z combinator et plutôt dérivée d'une autre

Question

Je travaillais pour dériver le Z-Combinator en commençant par la fonction factorielle et finit par dériver un autre point fixe combinator.Qu'ai-je tirer?J'ai fait une erreur subtile?

Voici les étapes que j'ai effectuées (en JavaScript)

1.Déclarer la fonction factorielle

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

2.Convertir combinator (fermé expression)

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

3.Fil auto appel

Basée sur la signature fact(?, 7), en passant fact en tant que premier argument semble raisonnable fact(fact,7).Fil le paramètre par la queue composez le:

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

L'utilisation est maintenant fact(fact,7) → 5040

4.Refactoriser pour le curry de forme

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

5.Déplacer l'application locale de la déclaration de

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

6.Convertir laissez déclaration à l'expression lambda

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

L'utilisation est encore fact(fact)(7) → 5040

7.Séparer la factorielle d'expression

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

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

8.Déplacer l'auto-application à partir de l'appelant pour le corps

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'utilisation est maintenant fact(7) → 5040

9.Convertir laissez déclaration à l'expression 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.Simplifier l'expression

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

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

Vérification générale.L'utilisation est encore fact(7) → 5040

11.Renommer les variables

L'utilisation de innerFact et self regarder étrangement similaire.Renommer à la même variable pour découvrir un modèle.Séparer lexicale étendues donc fort à faire:

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

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

12.Résumé _fact l'utilisation et le renommer fact

Renommer fact pour setup et l'abstrait _fact dans le corps par le remplacement, avec le paramètre 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)

Pas besoin de séparer _fact déclaration afin en ligne:

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.Renommer setup

Renommer ce à quoi?Ce combinateur est-ce?Selon Wikipédia Le Z combinator est:

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

Mais ce que j'ai dérivé est:

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

La définition de fact en termes de semble équivalent dans le comportement.Ai-je fais une erreur?Je n'ai accidentellement redécouvrir un autre bien connu combinator?

Answer 1

Si je inline (u => (f)(n => u(u)(n))) en (u => u(u)) J'obtiens:

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

Ce qui est exactement le Z-Combinator.

De wikipedia:

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

Mon calcul:

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