Анонимная рекурсивная функция в Scala

Question

Есть ли способ написать анонимную функцию, которая является рекурсивной в Scala? Я думаю о чем-то вроде этого:

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

(Похожие вопросы: Какие языки поддерживают * рекурсивные * функциональные литералы / анонимные функции? )

Answer 1

Как описано в ссылке, которую вы разместили.Вы можете использовать Y-комбинатор.Вот пример:

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

Обратите внимание, что он не работает с большими числами.Будьте осторожны с оптимизацией хвостового вызова.

Answer 2

Если вы не хотите использовать «Удивительную математику», вы можете просто вернуться к объектным аспектам scala.

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

Answer 3

, чтобы сделать его более странным, вы также можете использовать этот стиль кода:

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

Answer 4

В дополнение ко многим хорошим ответам здесь в этой теме, тот факт, что Scala не дает нам оптимизируемый хвостовой вызов комбинатора с фиксированной запятой, беспокоит меня так сильно, что я решил написать макрос для перевода Y-комбинатора-подобный вызов обычного идиоматического рекурсивного вызова (с оптимизацией хвостового вызова, конечно).Идея заключается в том, что вызов типа

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

легко переводится в

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

. Я включил реализацию макросов, ориентированную на Scala 2.11 (с незначительной настройкой, которая также должна работать с 2.10) в это суть .

С помощью этого макроса мы можем выполнять обычные рекурсивные задачи анонимно, не опасаясь переполнения стека, например:

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

дает

res0: BigInt = 33162750924506332411753933805763240382811...

Answer 5

Очень простой подход:

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)