scalaでYコンビネータ

Yコンビネータの定義:

def Y[A,B]( f:((A => B), A ) => B, x:A ):B = f( ( y:A ) => Y( f,y ),x ) 

Yコンビネータってのは、要は

Y(f) = f(Y(f))

となる関数らしい。不動点演算子とか呼ばれていますがなんのことかわかりませんね。

「ある関数fをYに与えた結果できる関数をf'とすると、f'をまたYに与えてできる関数はfと同じ」になるように関数を作り出すものです。

何でこんなもん必要なの?

ある無名関数があるとしましょう。この無名関数は名前が定義されていないため、自身を再帰で呼び出す定義ができません。

単純に、0から引数nまで加算する関数を無名関数で定義しようとすると、

(i:Int) => i match{
  case 0 => 0
  case _ => i + ここで自分自身を再帰で呼びたいけど名前がない( i - 1 )
}

こんな風に名前がないのでできませんよね?

ここで、Yコンビネータ様の登場ですよ!!

Yコンビネータ様は、引数にもらった無名関数を変換して、無名関数自身に便宜的な名前(さっきの例ではf)をつけて引数に渡す関数を作ってくれます。

そうすると、Yコンビネータに渡す無名関数は、Yコンビネータが引数でもらうはずの自分自身をfという引数名でもらえるようになっているので、無名関数内でfという名前を使って自分自身を再帰で呼び出すことができます。

さっきの、無名関数では再帰が定義できない、という問題はYコンビネータにより解決されました。

もともとは、ラムダ式で再帰を定義するための物らしいです。ラムダで条件分岐と繰り返しが定義できれば、あらゆる計算はラムダ式で実現できるという。。。

フィボナッチをやってみる

scala> def Y[A,B]( f:((A => B), A ) => B, x:A ):B = f( (y:A) => Y(f,y),x)              
Y: [A,B](((A) => B, A) => B,A)B

scala> Y( (f:Int => Int , n:Int) => n match{
     |     case m if m < 2 => m
     |     case _ => f( n - 1 ) + f( n - 2 )
     | },7)
res2: Int = 13

これはフィボナッチ数を計算するfという関数があって、fを再帰で呼び出しているように見えますが、実はYに与えた関数自身には名前がありません。

無名関数で再帰できてますね。

ってことで、自分では理解したつもりですが、書いてみると難すぃ。。。