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宣言をラムダ式に変換する

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宣言をラムダ式に変換する

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)))