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)