Anonymous recursive function in Scala

Question

Is there a way to write an anonymous function recursive in Scala? I am thinking of something like this:

((t: Tree) => { print(t.value); for (c <- t.children) thisMethod(c) })(root) 

(A related question: Which languages ​​support * recursive * literal / anonymous function functions? )

Answer 1

As described in the link you posted. You can use the Y-combinator. Here is an example:

 scala> def fix[A,B](f: (A=>B)=>(A=>B)): A=>B = f(fix(f))(_) fix: [A,B](f: ((A) => B) => (A) => B)(A) => B scala> val fact = fix[Int,Int](f => a => if(a<=0) 1 else f(a-1) * a) fact: (Int) => Int = <function1> scala> fact(12) res0: Int = 479001600 

Please note that it does not work with large numbers. Be careful when optimizing the tail call.

Answer 2

If you don't want to get into Amazing Maths, you can simply return to the object aspects of scala.

 val fact = new Function1[Int,Int]{ def apply(x:Int):Int = if(x==1) x else x * apply(x-1) } 

Answer 3

to make it look geekier, you can also use this code style:

 val fact = new ((Int) => Int){ def apply(x:Int):Int = if(x==1) x else x * apply(x-1) } 

Answer 4

Adding to the many good answers here in this thread, the fact that Scala does not give us an optimized fixed-point tail combinator has bothered me so much that I decided to write a macro to translate Y-combinator a similar call to a regular, idiomatic recursive call ( Of course, with tail call optimization). The idea is that a call like

 fix[Int,Int]((next) => (y) => ...body...) 

easily translates to

 ({(input) => object next { def apply(y:Int):Int = ...body... } next(input) }) 

I applied the implementation of the Scala 2.11 macro (with a slight change should also work with 2.10) in this sense .

With this macro, we can perform ordinary recursive tasks anonymously without fear, for example.

 import asia.blip.ymacro.YMacro._ (y[BigInt,BigInt]((xx) => (y) => if(y==1) 1 else y * xx(y-1)))(2000) 

gives

 res0: BigInt = 33162750924506332411753933805763240382811... 

Answer 5

A very simple approach:

 val fact = { (x: Int) => def f(x: Int): Int = if (x == 0) 1 else x * f(x-1) f(x) } // Use as anonymous function below (1 to 5).map { (x: Int) => def f(x: Int): Int = if (x == 0) 1 else x * f(x-1) f(x) } // res0: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 6, 24, 120)