Как использовать TailCalls? - PullRequest
Новая
       21

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

19 голосов
/ 13 декабря 2010

Если я правильно понимаю, 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 ]

27 голосов
/ 13 декабря 2010

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

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

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

4 голосов
/ 28 августа 2016

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

...