Yコンビネータてなに
不動点コンビネータの一つです。
不動点コンビネータ？
関数に不動点が存在するとします。
その時不動点座標xにおいて関数fにたいして
f(x) = x
が成り立つといいます。
これを少し拡張して、引数を数値ではなく関数にして関数にたいして成り立つようなとき、関数gが不動点コンビネータなら
f(g(f)) = g(f)
が成り立つといいます。なんとなくわかったような気がします。つまり自分自身に対してコンビネータが入力値をそのまま出力していくので、評価していけば無限に実行できそうですよね。
何がいいの
不動点コンビネータが再帰関数としての特性をもつということです。実際に再帰的な処理を意識しなくても
条件を満たす関数を不動点コンビネータに投げ込むことで再帰処理をつくることができます。
この不動点コンビネータが再帰関数としての性質を持つことを簡単に証明してみましょう(Wikipedia参照)
ある関数a(x)が存在して、それが再帰関数ならば、定義のなかに自分自身が含まれるはずです。すなわち、
a(x) = U(a,x)
のような定義になるはずですよね。ここでUをカリー化した関数Vを定義してみましょう
カリー化とは、関数の引数を一つに減らすこと
V(f)(x) = U(f,x)
とします。ここで、もし関数gが存在して、この関数Vに対して不動点コンビネータとして成り立つようなら
V(g(V)) = g(V)
が成り立つはずなので、またg(V)もxの関数だから
g(V)(x) = V(g(V))(x) = U(g(V),x)
今、さきほどのaの式と上の式を比較すると
a=g(V)
の関係があるとわかります。したがって、この不動点コンビネータは再帰関数の特徴をもっていることがわかりますね。