Curry の不動点演算子のつくり方

前回の記事で YM = M(YM) となるような、関数Mの不動点を作り出す関数 Y があると、ラムダ記法でも再帰関数の定義ができることを説明した。今回は、そのような関数のひとつのCurry の不動点演算子の作り方を考えてみる。

Curryの不動点演算子の説明の前に、ラムダ記法をおさらいしてみる。ラムダ記法では、λx. (x + y) のようにλでその関数の変数がどれであるかを指示する。またラムダ式をMという記号で表した場合、前述のようなラムダ記法で記述した関数を意味する。ラムダ式の関数の変数に数値や関数を代入することをβ変換という。M= λx .(x+y)のとき、Ma = a + y だ。λ式ではこのようにλ式MとNを並べて書いた場合、MNはMという関数にNという関数を適用することを示している。

さて、λ式であらわされる次のような関数 I を考えてみよう。

I = λx . x

この関数 I では明らかに、どんな a についても Ia = a であるから、任意の要素は関数 I の不動点である。

それでは、次の関数 A はどうだろうか。

A = λx . xx

xx はλ式では x(x) のように変数xを関数xに代入することになるから、自己適用していることになる。このような関数 A にそれ自身を引数として与えると、

AA = λx . xx (A) = AA

のようになって、β変換後も変化しない。つまり、β変換の操作に対して不動点となっている。このAを任意の関数Mに適用させて合成関数を作ってみる。すると、

MA = M(xx)

なので、MAにMAを自己適用してみると、

(MA)(MA) = (M(λx. xx))(MA) = M((MA)(MA))

のように(MA)(MA)がMの不動点になっていることがわかる。なぜそうなるかと聞かれてもわからないが、やっていることは記号の置き換えだけなので不明なところはない。上の(MA)(MA)をλ記法で詳しく書くと、

(MA)(MA) = (λx . M(xx)) (λx. M(xx))

となる、上の式でMは任意の関数だから、これを変数 y として関数抽象すると次の関数 Y ができあがる。

Y = λy . (λx . y(xx)) (λx. y(xx))

これが、Curry の不動点演算子(Y コンビネータ)で、これに任意の関数Mを適用した YM は次のように、関数Mの不動点になる。

YM = M(YM)

ラムダ計算では、このようなコンビネータは無数にあるが、どれも関数の不動点を作り出す。

Haskell で Y コンビネータの試験をしてみた。

Hugs> y fact 5 where y f = f (y f); fact f n = if n == 0 then 1 else n * f (n-1)
120

コンビネータの定義を、y f = f (y f) と関数名を使った再帰的定義をしているが、ラムダ記法だけで記述したコンビネータと動作は変わらない。Haskell では型推定の関係で、ラムダ記述そのままのコンビネータは書けない。重要なのは、fact の定義に関数名を使わずに済んでいることだ。コンビネータの定義で関数名による定義が行われたのに目をつぶれば、無名再帰が Haskell でも行うことができるのがわかる。実際に、次のようにすれば、無名関数をもちいて再帰関数が記述できるのがわかる。

Hugs> y (\f n -> if n == 0 then 1 else n * f (n-1)) 5 where y f = f (y f)
120

Yコンビネータには実用的な意味はあまりない。しかし、ラムダ記法で再帰的関数の定義ができることを証明する。手続き型言語と関数型言語は同じようにコンピュータで計算できる関数を記述できることの証明のひとつとなっている。

[追記]

不動点コンビネータは、Haskell の Control.Monad.Fix モジュールに fix という関数名で含まれていた。

Hugs> :l Control.Monad.Fix
Control.Monad.Fix> fix (\f n -> if n == 0 then 1 else n * f (n-1)) 5
120
[PR]
by tnomura9 | 2011-06-05 03:33 | Haskell | Comments(0)
<< 配列をスライスする。 Curry の不動点演算子 >>