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
やってるのはフィボナッチ。
- 追記
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
関数を受け取って関数を返す関数を受け取って関数を返す関数・・・・