YコンビネータをSKIコンビネータから作る
Yコンビネータとは
不動点コンビネータと呼ばれるものの1つ
関数型プログラミングにおける再帰、つまるところループのようなもの
普通再帰呼び出しを行うには関数に名前をつけ、その名前をその関数自身の中で呼び出すことで行う
無名関数ではそれが出来ないので再帰させたい部分関数を引数に取り、それを繰り返す関数を作る必要がある
具体的にはこのような性質を持つ
Yf = f(Yf)
Yコンビネータ以外にも似たような性質を持った不動点コンビネータは存在する
作ってみよう
いきなりYf=f(Yf)を満たすのは難しかったのでY'=fY'（Y'はfを含む式）と仮置きします
まずは基本を再確認
Sxyz = xz(yz)
Kxy = x
Ix = x
複製する関数
SIIx=Ix(Ix)=xx
今回は引数なるfを複製するので上の式を利用したい
で、IやKxは複製しても情報量が増えないのでSxyを複製してみる
SII(Sxy) = Sxy(Sxy) = x(Sxy)(y(Sxy))
y = SIIとおくと後半部分が最初の式と一致する
SII(Sx(SII))=x(Sx(SII))(SII(Sx(SII))
前半部分をY'と一致させる
x(Sx(SII)) = f
x = Kf（Kf(S(Kf)(SII)) = f）
Y'=SII(S(Kf)(SII))
実際に確かめてみる
Y' = SII(S(Kf)(SII))
= S(Kf)(SII)(S(Kf)(SII))
= Kf(S(Kf)(SII))(SII(S(Kf)(SII)))
=f(SII(S(Kf)(SII))) = fY'
内側にいるfを一番後ろまで掘り出す
Yf = Y' = SII(Af)となるようにAをおく
Yf = S(K(SII))Af
Y = S(K(SII))A
Af = Bf(SII)となるようにBをおく
Af=SB(K(SII))f
A=SB(K(SII))
Bf = S(Kf)
Bf = S(KS)Kf
B = S(KS)K
A=S(S(KS)K)(K(SII))
Y=S(K(SII))(S(S(KS)K)(K(SII)))
実際に確かめてみる
Yf=S(K(SII))(S(S(KS)K)(K(SII)))f
= K(SII)f(S(S(KS)K)(K(SII))f)
= SII(S(S(KS)K)(K(SII))f)
= S(S(KS)K)(K(SII))f(S(S(KS)K)(K(SII))f)
= S(KS)Kf(K(SII)f)(S(S(KS)K)(K(SII))f)
= KSf(Kf)(K(SII)f)(S(S(KS)K)(K(SII))f)
= S(Kf)(K(SII)f)(S(S(KS)K)(K(SII))f)
= Kf(S(S(KS)K)(K(SII))f)(K(SII)f(S(S(KS)K)(K(SII))f))
= f(K(SII)f(S(S(KS)K)(K(SII))f))
ここの後半が二行目と一致
= f(S(K(SII))(S(S(KS)K)(K(SII)))f)
=f(Yf)