Как использовать TailCalls?

Если я правильно понимаю, scala.util.control.TailCalls можно использовать, чтобы избежать для не хвостовых рекурсивных функций, используя батут. Пример, приведенный в API, прост:

import scala.util.control.TailCalls._

def isEven(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

def isOdd(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

isEven((1 to 100000).toList).result

Однако более интересным является случай, если вы хотите выполнить некоторые операции после вызова recursve. Я получил "наивную" факториальную реализацию, как-то запущенную

def fac(n:Long): TailRec[Long] = 
    if (n == 0) done(1) else done(n * tailcall(fac(n - 1)).result)

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

Ответ 1

Да, ваш наивный факториал не будет хвостом рекурсивным и будет использовать пространство стека, линейное по значению аргумента. Цель scala.util.control.TailCalls - не волшебным образом превращать нередуцирующие алгоритмы в хвостовые рекурсивные. Цель состоит в том, чтобы циклы взаимно-хвостовых функций выполнялись в постоянном пространстве стека.

Компилятор Scala реализует оптимизацию хвостовой рекурсии для методов, которые вызывают себя в хвостовом положении, позволяя стеку стека вызывающего метода использоваться вызывающим. Он делает это, по существу, путем преобразования доказуемого хвостового рекурсивного вызова в цикл while под крышками. Однако из-за ограничений JVM нет возможности реализовать оптимизацию хвостового вызова, что позволило бы любому методу вызывать в хвостовом положении повторное использование кадра стека вызывающего абонента. Это означает, что если у вас есть два или более метода, которые называют друг друга в позиции хвоста, оптимизация не будет выполнена, и переполнение стека будет рисковано. scala.util.control.TailCalls - это взлом, позволяющий обойти эту проблему.

Кстати, стоит посмотреть источник на scala.util.control.TailCalls. Вызов "результат" - это то место, где выполняется вся интересная работа, и в основном внутри всего цикла.

Ответ 2

Этот вопрос более 6 лет, но принятый ответ, похоже, не отвечает на вопрос:

Итак, мой вопрос заключается в том, как правильно писать факториал или функцию фибоначчи с помощью TailCalls (да, я знаю, как использовать аккумуляторы, чтобы получить их хвост-рекурсивный)?

Итак, вот он:

object Factorial {

  /**
    * Returns the nth factorial
    */
  def apply(n: Long): BigInt = {
    if (n < 0)
      throw new IllegalArgumentException("Can't factorial to an index less than 0")
    else {
      import scala.util.control.TailCalls._
      def step(current: Long): TailRec[BigInt] = {
        if (current <= 0)
          done(1)
        else
          tailcall {
            for {
              next <- step(current - 1)
            } yield current * next
          }
      }
      step(n).result
    }
  }

}

assert(Factorial(0) == 1)
assert(Factorial(7) == 5040)
assert(Factorial(10) == 3628800)

Один из больших вариантов использования TailCalls - это сделать что-то похожее на обратную сторону.