Y(Z)コンビネータ

無名関数が再帰できるとか。

scala> def Y[A,B](f:(A=>B)=>(A=>B))(x:A):B = f(Y(f))(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)
res1: Int = 13

やってるのはフィボナッチ。

参考:
scalaでYコンビネータ - ゆろよろ日記

  • 追記

Yって書いたこれは実はZコンビネータってやつで、本物のYコンビネータはこんな感じ。

scala> def Y[A,B](f:(A=>B)=>(A=>B)):A=>B = f(Y(f))
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)
java.lang.StackOverflowError
        at .Y(<console>:4)
        at .Y(<console>:4...


Zコンビネータのやつを書き直すとこんな感じ。

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

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


関数を受け取って関数を返す関数を受け取って関数を返す関数・・・・