Curry の不動点演算子

いま、関数 f があったとして、その f にある要素 a を適用すると関数の値がその要素と一致する場合、つまり、a = f(a) となる場合、この a を関数 f の不動点という。たとえば、f(x) = 2 * x のとき、x = 0 は f(0) = 0 なので f(x) の不動点だ。

ラムダ記法や関数型プログラミング言語では関数を引数とする関数(高階関数)を考えることができるから、高階関数の不動点、たとえば、g(x) = f(g(x)) となるような、g(x) を考えることができる。f(g(x)) は関数だから、変数 x に値 n を適用すると上の式は g(n) = f(g(n)) となる。

ところで、g(x) = f(g(x)) なので、右辺の g(x) を展開すると g(x) = f(f(gx)) である。この展開をもっと続けると、

g(x) = f(f(f(f(f(f(f(f .. f(gx)) .. ))))))

とあわせ鏡のようにどれだけでも入れ子になった関数で g(x) を記述できる。これは、f(x) が関数を引数とする高階関数だからできる芸当だ。

ここで、Yという高階関数を考えてみる。このYに任意のMという関数を適用した Y(M) という関数は、Mの不動点になってしまうとする。つまり、

Y(M) = M(Y(M))

だ。上の式はどんな関数M に対しても Y(M) が M の不動点になるということを示している。このような都合のいい関数 Y が存在するかどうかは後で考えるが、このような Y があるとき何が起きるだろうか。

今 M(f) = i * f (i - 1) という関数 f を引数とする高階関数を考える。これを関数Yに適用させた関数Y(M)はMの不動点になるので、

Y(M(f)) = M(Y(M(f))) = i * (Y(M(f))) (i - 1)

したがって、Y(M(f))に整数 n を適用させると、

Y(M(f)) (n) = n * (Y(M(f))) (n - 1)

となる。ここで、Y(M(f)) = fact と置くと、

fact(n) = n * fact(n-1)

のように、おなじみの階乗のプログラムになる。このYという関数は色々あるが、Curry の Y コンビネータが有名だ。ラムダ記法で定義される関数は無名関数だ。したがって、関数名を利用する再帰的定義はできないが、このYコンビネータによって、無名再帰関数を記述することができる。このおかげで、コンピュータで計算できる全てのプログラムはラムダ記法で記述できることが分かる。
[PR]
by tnomura9 | 2011-06-04 11:18 | Haskell | Comments(0)
<< Curry の不動点演算子のつくり方 自己適用 >>