尝试导出 Z 组合器，而是导出另一个

Question

我致力于从阶乘函数开始导出 Z 组合器，最终导出了一个不同的定点组合器。我得到了什么？我犯了一个微妙的错误吗？

这是我执行的步骤（在 JavaScript 中）

1.声明阶乘函数

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

2.转换为组合器（闭合表达式）

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

3.线程自调用

根据签名 fact(?, 7), 通过 fact 因为第一个论点似乎合理 fact(fact,7). 。因此，将参数线程化到尾部调用：

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

现在使用情况是 fact(fact,7) → 5040

4.重构为柯里化形式

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

5.将自行申请移至本地声明

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

6.将 let 声明转换为 lambda 表达式

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

使用情况依旧 fact(fact)(7) → 5040

7.分离阶乘表达式

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

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

8.将自我应用程序从呼叫者转移到正文

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

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

现在使用情况是 fact(7) → 5040

9.将 let 声明转换为 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.简化表达

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

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

完整性检查。使用情况依旧 fact(7) → 5040

11.重命名变量

的用法 innerFact 和 self 看起来可疑地相似。重命名为同一变量以发现模式。单独的词法范围可以安全地执行：

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

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

12.抽象的 _fact 用法和重命名 fact

改名 fact 到 setup 和抽象 _fact 在正文中通过替换为参数 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)

无需单独 _fact 内联声明：

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.改名 setup

改名为什么？这是什么组合器？根据 维基百科 Z 组合器是：

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

但我得出的是：

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

定义 fact 两者在行为上似乎是相同的。我做错了吗？我是否无意中重新发现了另一个著名的组合器？

Answer 1

如果我内联 (u => (f)(n => u(u)(n))) 进入 (u => u(u)) 我得到：

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

这正是 Z-Combinator。

来自维基百科：

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

我的推导：

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