Anonyme en fonction récursive en Scala

Question

Est-il possible d'écrire une fonction anonyme qui est récursif dans Scala? Je suis en train de penser à quelque chose comme ceci:

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

(Liés à la question: Qui prend en charge les langues *récursive* littéraux de fonction / fonctions anonymes?)

Answer 1

A

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

N

Answer 2

Si vous ne voulez pas vous lancer dans les "mathématiques étonnantes", vous pouvez simplement revenir aux aspects objet de Scala.

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

Answer 3

Pour donner un aspect plus "geek", vous pouvez également utiliser ce style de code :

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

Answer 4

En plus des nombreuses bonnes réponses données dans ce fil, le fait que Scala ne nous donne pas de combinateur à point fixe optimisable par appel de queue m'a tellement ennuyé que j'ai décidé d'écrire une macro pour traduire un appel de type combinateur Y en un appel récursif ordinaire et idiomatique (avec optimisation par appel de queue, bien sûr). L'idée est qu'un appel comme

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

est facilement traduisible en

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

J'ai mis en place une macro implémentation pour Scala 2.11 (avec des modifications mineures, elle devrait aussi fonctionner avec 2.10) dans ce gist .

Avec cette macro, nous pouvons effectuer des tâches récursives ordinaires de manière anonyme sans craindre un débordement de la pile, par exemple

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

donne

res0: BigInt = 33162750924506332411753933805763240382811...

Answer 5

Appels récursifs en Scala. Prenons l'exemple de la somme de N nombres pour la récursivité

var sumIt:(Int => Int) = (x: Int) => {if(x<=1) 1 else sumIt(x-1)+x}

 scala> sumIt(10) 
val res141: Int = 55

Vous pouvez voir que le type de sumIt est Int, Int en entrée et la valeur de retour. La fonction lambda sumIt prend comme argument un entier et effectue un appel récursif sur sumIt.

Je me suis contenté de cet exemple pour faciliter la compréhension de l'appel à la récursivité. Vous pouvez utiliser une formule directe pour cette logique comme...

sumValue = (N*(N+1)) /2