先物テール再帰を含む関数を作成するにはどうすればよいですか？

Question

私のScalaアプリケーションでは、Future [T]型の結果を返す関数を呼び出す関数があります。私は私の再帰的な関数呼び出しでマッピングされた結果を渡す必要があります。これを尾を再帰的にしたいのですが、マップ（またはflatMap）がそのことを行う能力を壊しています。私はエラー "再帰的な呼び出しではないテールポジション"を取得します。

以下は、このシナリオの簡単な例です。この呼び出しを修正して、（Await.result（））を使ってFuturesのメリットを覆すことなく、コールが末尾に再帰的になるようにするにはどうすればよいですか？

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) 

Answer 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) 

ですから、スタックが実際に短いであることがわかります。これがスタック再帰の場合、factorialAccメソッドへの約97回の呼び出しを見たはずです。代わりに、1つのみを表示します。

Answer 2

メイクは、のIntを返すだけfactorial機能で、将来的にそれをラップfactorialAcc。

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) 
    } 
} 

はおそらく動作するはずです。

Answer 3

代わりにfoldLeftを使用するのはどうですか？

Answer 4

ここに、将来を返す別の関数を呼び出す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)