Scala Tail 递归未来 returns

Question

如何在 Scala 中使用 futures 作为 return 值实现尾递归函数：

示例代码

 def getInfo(lists: List[Int]): Future[List[Int]] = {
  def getStudentIDs(lists: List[Int]): Future[List[Int]] = {
    //here a web service call that returns a future WS response
        val response=ws.call(someURL)

        response.map(r => {
          r.status match {

            case 200 =>
              var newList = lists + (r.json \ ids)
                .as[List[Int]] //here add the ws call response json..
              getStudentIDs(newList)
            case 429 =>Future.sucessful(lists)
            case _ => getStudentIDs(lists)
          }

        })
      }
      getStudentIDs(List.empty[Int])
    }

Answer 1

这是问题所在（代码经过简化以使其可运行）：

import scala.concurrent._
import scala.concurrent.duration._
import annotation.tailrec   
import scala.concurrent.ExecutionContext.Implicits.global

 def getInfo(lists: List[Int]): Future[List[Int]] = {
  @tailrec
  def getStudentIDs(lists: List[Int]): Future[List[Int]] = {
     Future(List(1, 2, 3)).flatMap(x => getStudentIDs(x ::: lists))
  }
     getStudentIDs(List.empty[Int])
  }

报错：

error: could not optimize @tailrec annotated method getStudentIDs: 
it contains a recursive call not in tail position
            Future(1).flatMap(x => getStudentIDs(x :: lists))
                      ^

问题不仅仅在于 Future。实际问题是 getStudents 不在 terminal/tail 位置 - 它是从 map 调用的。如果您不使用 Futures 而是使用集合中的常规 map 或与此相关的任何其他函数，这将是一个问题。例如：

 def getInfo(lists: List[Int]): List[Int] = {
  @tailrec
  def getStudentIDs(lists: List[Int]): List[Int] = {
     List(1).flatMap(x => getStudentIDs(x :: lists))
  }
     getStudentIDs(List.empty[Int])
  }

给出同样的错误：

error: could not optimize @tailrec annotated method getStudentIDs:
it contains a recursive call not in tail position
            List(1).flatMap(x => getStudentIDs(x :: lists))
                    ^

这里的困难在于，您不能直接从 future 中获取结果以在 getStudents 中使用它，因为您不知道它是否已完成，并且阻止它不是一个好习惯未来，等待结果。所以你有点被迫使用 map。这是一个非常糟糕的例子，说明如何使其尾递归（仅用于科学:)）。不要在生产代码中这样做：

 def getInfo(lists: List[Int]): Future[List[Int]] = {
  @tailrec
  def getStudentIDs(lists: List[Int]): Future[List[Int]] = {
     val r = Await.ready(Future(List(1, 2, 3)), Duration.Inf).value.get.getOrElse(lists)
     getStudentIDs(r ::: lists)
  }
     getStudentIDs(List.empty[Int])
  }

编译器很高兴，但这可能会导致许多问题 - 请阅读 Await、blocking 和线程池以了解更多信息。

我认为您的函数不是尾递归可能不是什么大问题，因为您可能无论如何都不想以这种方式创建很多期货。如果这真的是一个问题，比如 actors (Akka) 等，您可以尝试其他并发框架

Answer 2

我认为是 XY-problem。在 "having a @tailrec" 注释的意义上，您可能不想要它 "tail-recursive"。你想要的是堆栈安全，这样在重试数百次连接到你的网络服务后，此方法不会破坏堆栈。

为此，有库，例如 Cats。

在 Cats 中，有一个名为 Monad 的类型类，这个类型类提供了一个特殊的方法，似乎正是您想要的：

 tailRecM[A, B](a: A)(f: (A) => F[Either[A, B]]): F[B]

引自文档：

Keeps calling f until a scala.util.Right[B] is returned. Implementations of this method should use constant stack space [...]

Future in FutureInstances available. The implementation seems trivial though, because it mixes in StackSafeMonad.

有一个实现

您当然可以查看 StackSafeMonad 的实现，然后尝试理解为什么它在 Future 的情况下就足够了，但您也可以只使用库实现而不是担心您的递归方法是否会因 WhosebugError.

而失败

Scala Tail 递归未来 returns

Scala Tail recursion future returns

scala

future

tail-recursion