再帰してみる

以前から何度か自分でもラムダのみで再帰（Yコンビネータ）を導きだしてみようと挑戦していたのだが、結局作れずじまいだった。しかしLazy Kで書いてみると意外にも書けてしまった。
まずはこれ。

sii(sii)

これはいくらやってもsii(sii)になる。まぁこれだけだと任意の関数を評価することはできないので、これを基に、sAB(sAB)という関数を考え、sAB(sAB)Xを最外簡約していくとX(sAB(sAB)X)となるように作ればよい。というわけで早速トライ。

sAB(sAB)X
A(sAB)`B(sAB)X
s(ki(sAB))`B(sAB)X   # AXをs(kiX)とする
ki(sAB)X(B(sAB)X)
X(B(sAB)X)
X(sii(sAB)X)         # Bを(sii)とする
X(sAB(sAB)X)

ここまででBは求まった。あと書いてて気付いたんだがsAB(sAB)とはsii(sAB)である。なので、sii(sAB)XがX(sii(sAB)X)というふうになればよい。
というか上の最後の簡約は最外じゃない。やるんならXを(sAB(sAB)X)に適用するのが先。なので改めて書いてみる。

sii(sAB)X
sAB(sAB)X
A(sAB)`B(sAB)X
s(ki(sAB))`B(sAB)X   # AXをs(kiX)とする
ki(sAB)X(B(sAB)X)
X(B(sAB)X)
X(sii(sAB)X)         # Bを(sii)とする

次にAを求める。（面倒なのでBをsiiに置き換えない）。

s(ki(sAB))`B(sAB)X
ks(sAB)(ki(sAB))`B(sAB)X
s`ks`ki(sAB)`B(sAB)X

というわけでAは(s`ks`ki)となる。で、AとBをそれぞれの定義で置き換えてみると、

sii(s(s`ks`ki)(sii))
si`s(s`ks`ki)(sii)

となってめでたく再帰ができるようになった。やったね！