Yコンビネータ実装しなイカ？

Yコンビネータについて勉強しなイカ？

ということで、勉強してみました。

　まず、Yコンビネータとは何か？それを知るには、少し導入が必要になります。

数学的な話になりますが、不動点というものがあります。不動点とは、ある写像に対して自分自身に写される点のことです。例えば、f(x) = x^2という関数に対して、x = 0、x = 1という点は不動点です。（f(0) = 0、f(1) = 1だからです。）

　さて、上の説明では一階関数の不動点を例にとりました。同じように高階関数に対しても不動点が存在します。高階関数fと、別の関数pに対してf(p) = pが成り立つとき、関数pを関数fの不動点といいます。

関数gを入力に取り、関数gの不動点を返す高階関数を不動点コンビネータと呼びます。

　Y(g) = g(Y(g))

となるようなYが不動点コンビネータです。

そして、代表的な不動点コンビネータが、名字も名前も有名なかのハスケル・カリーさんが発見したYコンビネータ

　Y = λf.(λx.f (x x)) (λx.f (x x))　

です。

いきなりλが出てきて謎な感じですが、このλはλ算法と呼ばれるものです。λ算法では、関数x+2をλx.x+2のように書きます。また、λ算法は、カリー化された表現なので、x-yをλxy.x-yのように書きます。

Yコンビネータに関数gを適用させてみます。

　Yg = (λx. g(x x)) (λx. g(x x))

　　= g ((λx. g(x x)) (λx. g(x x)))

　　 = g (Yg)

となります。1行目から2行目にかけては、β簡約が行われています。

　では、HaskellでYコンビネータを実装してみます。

しかし、Haskellでは遅延評価のおかげで、不動点コンビネータがそのまま書けてしまえます。Haskell神です。みんなもHaskell使ってみなイカ？

fix :: (t -> t) -> t
fix f = f (fix f)

のように定義します。この定義により、明らかにfixは関数fの不動点コンビネータになっています。

プログラミングの世界では、不動点コンビネータを利用することにより、無名再帰ができます。名前のないはずの関数が、名前のないはずの自分自身を呼び出すというちょっと奇妙なトリックですが、以下のようにできます。

main = print $
　　　　(fix (\f x -> if x == 0 then 1 else x * f (x-1))) 10

上のmainアクションでは、10の階乗を出力しています。

ここでポイントとなるのは、無名関数の書き方です。

普通、階乗を書くとしたら、

fact = \x -> if x == 0 then 1 else x * fact (x-1)

ですが、不動点コンビータで使用するためには、

fact = \f x -> if x == 0 then 1 else x * f (x-1)

のように書きます。

関数がどのように簡約されていくかをみれば、なぜこのような書き方をするのかが分かります。

(fix fact) 10

⇒ fact (fix fact) 10

⇒ 10 * ((fix fact) 9)

⇒ 10 * (fact (fix fact) 9)

⇒ 10 * (9 * ((fix fact) 8))

・・・・

で10の階乗が計算できるわけです。

　しかし、この書き方だと、fix自身が名前付きの再帰となっていて、ちょっとインチキくさいです。

ここの記事にも、同じようなことが書いてありました。

「ラムダ計算がチューリング完全であることを示すのが目的であれば、この定義はインチキです。」

うわっ、なんかすごい学術的な言葉が出てきた。以下wikipediaから引用。

"チューリング完全とは、あるプログラミング言語がチーリング機械と同じ計算能力を持つときその言語はチューリング完全であるという。"

な、なるほど。ここで言いたいのは、ラムダ計算には名前付き再帰がないにも関わらず、名前付きの再帰を使っていては、チューリング完全を満たさない。ということでしょう。。先のブログでは、無名関数による実装が紹介されていました。

自分も、もう少しHaskell力がついたらチャレンジしたいです。