SKIコンビネータ
$ SKI（サムネ用）
SKIコンビネータ
この関数の構造も根源的な以下の3つの関数の組み合わせのみで表現できる
$ S = \lambda xyz.xz(yz)
$ K = \lambda xy.x
$ I = \lambda x.x
実のところ$ I = SKKなので$ Iは必要無いのだが、あったほうが便利なので入っている
実は$ Sと$ Kもたった1つのコンビネータの組み合わせで置換できるので、万物はたった1つの関数の構造だけで表現できるということになる
根源的な少ないコマンドしか持たないという点で「手続型プログラミング言語におけるbrainf*ck」に対して「関数型プログラミング言語におけるSKIコンビネータ」と言うことができる
SKI以外にもBCKWとかもある
やってみる
この式をラムダ式に置換えてみる$ S(K(SI))K
とりあえず適当な変数xを適用してみる
$ (S(K(SI))K)x = K(SI)x(Kx) = SI(Kx)
まだSKIが残っているので追加でyを適用してみる
$ SI(Kx)y = Iy(Kxy) = y(Kxy) = yx
$ \therefore S(K(SI))K = \lambda xy.yx
この式をSKIに置き換えてみる$ \lambda fx.f(fx)
$ Afx = f(fx)となるように$ Aを仮置きする
まずはxから消す
入れ子の内側にxを入れるにはSが使えそう
$ Af=SBCとすると
$ (SBC)x=Bx(Cx)
元の式$ Afx=f(fx)と比較して……
$ Bx = f = Kfx \Rightarrow B = Kf
$ Cx = fx \Rightarrow C = f
$ \therefore Af = S(Kf)f
$ A=SDEとすると
$ (SDE)f = Df(Ef)
$ Df = S(Kf) = (S(KS)K)f \Rightarrow D = S(KS)K
$ Ef = f = If \Rightarrow E = I
$ \therefore \lambda fx.f(fx) = S(S(KS)K)I