Как использовать 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

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

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

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

Источник

2 ответа

Решение

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

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

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

Источник

Этому вопросу более 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 - сделать что-то похожее на правую.

Источник
Другие вопросы по тегам