Tentou derivar a Z combinator e, em vez de derivada de outra

Question

Eu estava trabalhando para derivar a Z-Combinator, iniciando com a função fatorial e acabou derivando de um diferente ponto fixo combinator.O que eu fiz de derivar?Que eu faça uma sutil engano?

Aqui estão os passos que eu fiz (em JavaScript)

1.Declarar a função fatorial

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

2.Converter para combinator (fechado expressão)

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

3.O Thread de chamada auto

Com base em assinatura fact(?, 7), passando fact como primeiro argumento parece razoável fact(fact,7).Assim, o parâmetro thread através da chamada de cauda:

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

O uso é agora fact(fact,7) → 5040

4.Refatorar para caril forma

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

5.Mover auto aplicação local de declaração

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

6.Converter deixe declaração de expressão lambda

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

O uso é ainda fact(fact)(7) → 5040

7.Separar o fatorial de expressão

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

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

8.Mover a auto-aplicação do chamador para o 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)
})()

O uso é agora fact(7) → 5040

9.Converter deixe declaração de expressão 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 a expressão

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

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

Verificação de sanidade.O uso é ainda fact(7) → 5040

11.Mudar o nome das variáveis

O uso de innerFact e self olhar suspeito semelhantes.Mude para a mesma variável para descobrir um padrão.Separado lexical escopos de modo seguro para o fazer:

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

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

12.Resumo _fact uso e mudar o nome fact

Mudar o nome fact para setup e abstratos _fact no corpo, substituindo com 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)

Não há necessidade de separar _fact declaração 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.Mudar o nome setup

Mude o nome para o que?O que combinator é isto?De acordo com a Taxas O Z combinator é:

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

Mas o que eu tenho derivada é:

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

Definição fact em termos de parece equivalente no comportamento.Eu cometer um erro?Eu acidentalmente redescobrir outro bem conhecido combinator?

Answer 1

Se eu inline (u => (f)(n => u(u)(n))) em (u => u(u)) Eu recebo:

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

O que é exatamente a Z-Combinator.

Da wikipedia:

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

Meu derivação:

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