Jak utworzyć funkcję obejmującą rekurencję tail futures?

Question

W mojej aplikacji Scala, mam funkcję, która wywołuje funkcję, która zwraca wynik typu Future [T]. Muszę przekazać zmapowany wynik w rekurencyjnym wywołaniu funkcji. Chcę, aby to było rekurencyjne, ale mapa (lub flatMap) uniemożliwia to. Pojawia się błąd "Wywołanie rekurencyjne nie w pozycji ogonowej."

Poniżej znajduje się prosty przykład tego scenariusza. W jaki sposób można to zmodyfikować, aby wywołanie miało charakter rekursywny (bez podważania korzyści wynikających z kontraktów Futures za pomocą funkcji 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) 

Answer 1

mogę się mylić, ale czynność nie musi być ogon rekurencyjnej w tym przypadku.

Rekursja ogona pomaga nam nie zużywać stosu w przypadku korzystania z funkcji rekursywnych. W twoim przypadku jednak nie zużywamy stosu w taki sposób, jak typowa funkcja rekursywna.

Dzieje się tak dlatego, że wywołanie "rekursywne" nastąpi asynchronicznie, w jakimś wątku z kontekstu wykonania. Jest więc bardzo prawdopodobne, że to wywołanie rekurencyjne nie będzie nawet znajdować się na tym samym stosie, co pierwsze wywołanie.

Metoda factorialAcc utworzy przyszły obiekt, który w końcu asynchronicznie wywoła wywołanie "rekurencyjne". Następnie jest natychmiast wyskakiwany ze stosu.

Więc to nie jest rekursja stosu, a stos nie rośnie proporcjonalnie do n, pozostaje mniej więcej w stałym rozmiarze.

Możesz to łatwo sprawdzić, rzucając wyjątek w pewnym momencie metody factorialAcc i sprawdzając ślad stosu.

I przepisał swój program, aby uzyskać bardziej czytelny ślad stosu:

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) 

} 

a wyjście jest:

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) 

Więc widać, że stos jest rzeczywiście krótki. Jeśli był to rekurencja stosu, powinieneś zobaczyć około 97 wywołań do metody factorialAcc. Zamiast tego widzisz tylko jeden.

Answer 2

Producent factorialAcc powrócić int i tylko owinąć go w przyszłości w funkcji 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) 
    } 
} 

prawdopodobnie powinien działać.

Answer 3

A może zamiast tego używać metody foldLeft?

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

Answer 4

Oto rozwiązanie typu foldLeft, które wywołuje inną funkcję zwracającą przyszłość.

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)