Intenté derivar el combinador Z y en su lugar derivé otro

Question

Estaba trabajando para derivar el combinador Z comenzando con la función factorial y terminé derivando un combinador de punto fijo diferente.¿Qué deduje?¿Cometí un error sutil?

Estos son los pasos que realicé (en JavaScript)

1.Declarar función factorial

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

2.Convertir a combinador (expresión cerrada)

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

3.Autollamada del hilo

Basado en la firma fact(?, 7), pasando fact como primer argumento parece razonable fact(fact,7).Así que pase el parámetro a través de la llamada final:

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

El uso es ahora fact(fact,7) → 5040

4.Refactorizar a forma de curry

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

5.Pasar la autosolicitud a la declaración local

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

6.Convertir declaración let en expresión lambda

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

El uso aún es fact(fact)(7) → 5040

7.Separar la expresión factorial.

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

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

8.Mover la autoaplicación de la persona que llama al cuerpo

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

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

El uso es ahora fact(7) → 5040

9.Convertir declaración let en expresión 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.Simplificar expresión

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

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

Prueba de cordura.El uso aún es fact(7) → 5040

11.Cambiar el nombre de las variables

El uso de innerFact y self parecen sospechosamente similares.Cambie el nombre a la misma variable para descubrir un patrón.Separe ámbitos léxicos de forma segura:

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

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

12.Abstracto _fact uso y cambio de nombre fact

Rebautizar fact a setup y abstracto _fact en el cuerpo reemplazando con el parámetro 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)

No hay necesidad de separar _fact declaración tan en línea:

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

¿Cambiarle el nombre a qué?¿Qué combinador es este?De acuerdo a Wikipedia El combinador Z es:

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

Pero lo que he derivado es:

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

Definiendo fact en términos de cualquiera de los dos parece equivalente en comportamiento.¿He cometido un error?¿Redescubrí accidentalmente otro combinador conocido?

Answer 1

si estoy en línea (u => (f)(n => u(u)(n))) en (u => u(u)) Yo obtengo:

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

Que es exactamente el Z-Combinator.

De wikipedia:

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

Mi derivación:

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