Как сделать функцию с фьючерсным хвостом рекурсивным?

В моем приложении Scala у меня есть функция, которая вызывает функцию, которая возвращает результат типа Future [T]. Мне нужно передать отображаемый результат в мой вызов рекурсивной функции. Я хочу, чтобы это было хвостом рекурсивным, но карта (или flatMap) нарушает способность этого делать. Я получаю сообщение об ошибке "Рекурсивный вызов не в положении хвоста".

Ниже приведен простой пример этого сценария. Как это можно изменить так, чтобы вызов был хвостом рекурсивным (без подрыва преимуществ Futures с Await.result())?

import scala.annotation.tailrec
import scala.concurrent.{Await, Future}
import scala.concurrent.duration._

implicit val ec = scala.concurrent.ExecutionContext.global

object FactorialCalc {
  def factorial(n: Int): Future[Int] = {

    @tailrec
    def factorialAcc(acc: Int, n: Int): Future[Int] = {
      if (n <= 1) {
        Future.successful(acc)

      } else {
        val fNum = getFutureNumber(n)
        fNum.flatMap(num => factorialAcc(num * acc, num - 1))
      }
    }

    factorialAcc(1, n)
  }

  protected def getFutureNumber(n: Int) : Future[Int] = Future.successful(n)
}

Await.result(FactorialCalc.factorial(4), 5.seconds)

Ответы

Ответ 1

Возможно, я ошибаюсь, но в этом случае ваша функция не нуждается в рекурсивной коррекции.

Рекурсия хвоста помогает нам не потреблять стек в случае использования рекурсивных функций. В вашем случае, однако, мы фактически не потребляем стек так, как типичная рекурсивная функция.

Это происходит потому, что "рекурсивный" вызов будет выполняться асинхронно, в каком-то потоке из контекста выполнения. Поэтому очень вероятно, что этот рекурсивный вызов не будет находиться в том же стеке, что и первый вызов.

Метод factorialAcc создаст будущий объект, который в конечном итоге вызовет "рекурсивный" вызов асинхронно. После этого он сразу же выносится из стека.

Таким образом, это не фактическая рекурсия стека, и стек не растет пропорционально n, он остается грубым с постоянным размером.

Вы можете легко проверить это, бросив исключение в какой-то момент в методе factorialAcc и проверив трассировку стека.

Я переписал вашу программу, чтобы получить более читаемую трассировку стека:

object Main extends App {
  import scala.concurrent.{Await, Future}
  import scala.concurrent.duration._

  implicit val ec = scala.concurrent.ExecutionContext.global

  def factorialAcc(acc: Int, n: Int): Future[Int] = {

    if (n == 97)
      throw new Exception("n is 97")

    if (n <= 1) {
      Future.successful(acc)

    } else {
      val fNum = getFutureNumber(n)
      fNum.flatMap(num => factorialAcc(num * acc, num - 1))
    }
  }


  def factorial(n: Int): Future[Int] = {
      factorialAcc(1, n)
  }

  protected def getFutureNumber(n: Int) : Future[Int] = Future.successful(n)

  val r = Await.result(factorial(100), 5.seconds)
  println(r)

}

И результат:

Exception in thread "main" java.lang.Exception: n is 97
at test.Main$.factorialAcc(Main.scala:16)
at test.Main$$anonfun$factorialAcc$1.apply(Main.scala:23)
at test.Main$$anonfun$factorialAcc$1.apply(Main.scala:23)
at scala.concurrent.Future$$anonfun$flatMap$1.apply(Future.scala:278)
at scala.concurrent.Future$$anonfun$flatMap$1.apply(Future.scala:274)
at scala.concurrent.impl.CallbackRunnable.run(Promise.scala:29)
at scala.concurrent.impl.ExecutionContextImpl$$anon$3.exec(ExecutionContextImpl.scala:107)
at scala.concurrent.forkjoin.ForkJoinTask.doExec(ForkJoinTask.java:262)
at scala.concurrent.forkjoin.ForkJoinPool$WorkQueue.runTask(ForkJoinPool.java:975)
at scala.concurrent.forkjoin.ForkJoinPool.runWorker(ForkJoinPool.java:1478)
at scala.concurrent.forkjoin.ForkJoinWorkerThread.run(ForkJoinWorkerThread.java:104)

Итак, вы можете видеть, что стек на самом деле короткий. Если это была рекурсия стека, вы должны были увидеть около 97 вызовов метода factorialAcc. Вместо этого вы видите только один.

Ответ 2

Как насчет использования foldLeft?

def factorial(n: Int): Future[Int] = future {
  (1 to n).foldLeft(1) { _ * _ }
}

Ответ 3

Вот решение foldLeft, которое вызывает другую функцию, которая возвращает будущее.

def factorial(n: Int): Future[Int] =
  (1 to n).foldLeft(Future.successful(1)) {
    (f, n) => f.flatMap(a => getFutureNumber(n).map(b => a * b))
  }

def getFutureNumber(n: Int) : Future[Int] = Future.successful(n)

Ответ 4

Сделать factorialAcc возвращать Int и только обернуть его в будущем в функции factorial.

def factorial(n: Int): Future[Int] = {

    @tailrec
    def factorialAcc(acc: Int, n: Int): Int = {
      if (n <= 1) {
        acc
      } else {
        factorialAcc(n*acc,n-1)
      }
    }

    future {
      factorialAcc(1, n)
    }
}

вероятно, будет работать.