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

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

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

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

Ответы

Ответ 1

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

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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...

Ответ 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)