Función recursiva anónima en Scala

recursion anonymous-function

Question

¿Hay alguna manera de escribir una función anónima recursiva en Scala? Estoy pensando en algo como esto:

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

(Pregunta relacionada: ¿Qué idiomas admiten * recursivo * funciones literales / funciones anónimas? )

Answer 1

Agregando a las muchas buenas respuestas aquí en este hilo, el hecho de que Scala no nos está dando un optimizador de punto fijo optimizable nos ha estado molestando tanto que he decidido escribir una macro para traducir una llamada similar a Y-combinator a una llamada recursiva ordinaria, idiomática (con optimización de la cola de llamadas, por supuesto). La idea es que una llamada como

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

es fácilmente traducible en

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

He puesto meta macro implementación Scala 2.11 (con ajustes menores también debería funcionar con 2.10) en este sentido .

Con esta macro, podemos realizar tareas recursivas ordinarias de forma anónima sin temor al desbordamiento de pila, por ejemplo

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

da

res0: BigInt = 33162750924506332411753933805763240382811...

Answer 2

Como se describe en el enlace que publicó. Puedes usar Y-combinator. Aquí hay un ejemplo:

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

Tenga en cuenta que no funciona con grandes números. Tenga cuidado con la optimización de llamadas finales.

Answer 3

Si no desea presionar "Matemáticas asombrosas", puede volver a los aspectos del objeto de Scala.

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

Answer 4

Un enfoque muy simple:

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)

Answer 5

para que se vea más geek, también puedes usar este estilo de código:

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