18

一般来说，在“内部”单子中工作时，我很难弄清楚如何编写尾递归函数。这是一个简单的例子：

这是来自我正在编写的一个小型示例应用程序，以更好地理解 Scala 中的 FP。首先提示用户输入一个Team由 7Player秒组成的。这个函数递归地读取输入：

import cats.effect.{ExitCode, IO, IOApp}
import cats.implicits._

case class Player (name: String)
case class Team (players: List[Player])

/**
  * Reads a team of 7 players from the command line.
  * @return
  */
def readTeam: IO[Team] = {
  def go(team: Team): IO[Team] = { // here I'd like to add @tailrec
    if(team.players.size >= 7){
      IO(println("Enough players!!")) >>= (_ => IO(team))
    } else {
      for {
        player <- readPlayer
        team   <- go(Team(team.players :+ player))
      } yield team
    }
  }
  go(Team(Nil))
}

private def readPlayer: IO[Player] = ???

现在我想要实现的（主要用于教育目的）是能够@tailrec在def go(team: Team). 但是我不认为有可能将递归调用作为我的最后一个语句，因为据我所知，最后一个语句总是必须将我的“提升”Team到 IO 单子中。

任何提示将不胜感激。

4

1 回答 1

26

首先，这不是必需的，因为IO它是专门为支持堆栈安全的一元递归而设计的。从文档：

IO在其flatMap评估中被蹦蹦跳跳。这意味着您可以安全地调用flatMap任意深度的递归函数，而不必担心会炸毁堆栈……</p>

因此，即使您需要 70,000 名玩家而不是 7 名玩家（尽管此时您可能需要担心堆），您的实现在堆栈安全方面也可以正常工作。

但是，这并不能真正回答您的问题，当然甚至@tailrec从来没有必要，因为它所做的只是验证编译器正在执行您认为应该执行的操作。

虽然不可能以可以用 注释的方式编写此方法，但@tailrec您可以通过使用 Cats 获得类似的保证tailRecM。例如，以下内容等效于您的实现：

import cats.effect.IO
import cats.syntax.functor._

case class Player (name: String)
case class Team (players: List[Player])

// For the sake of example.
def readPlayer: IO[Player] = IO(Player("foo"))

/**
  * Reads a team of 7 players from the command line.
  * @return
  */
def readTeam: IO[Team] = cats.Monad[IO].tailRecM(Team(Nil)) {
  case team if team.players.size >= 7 =>
    IO(println("Enough players!!")).as(Right(team))
  case team =>
    readPlayer.map(player => Left(Team(team.players :+ player)))
}

这表示“从一个空团队开始并重复添加玩家，直到我们有必要的人数”，但没有任何明确的递归调用。只要 monad 实例是合法的（根据 Cats 的定义——有一些关于是否tailRecM属于 on的问题Monad），你就不必担心堆栈安全。

作为旁注，fa.as(b)相当于fa >>= (_ => IO(b))但更惯用。

另外作为旁注（但可能更有趣），您可以更简洁地编写此方法（并且在我看来更清楚），如下所示：

import cats.effect.IO
import cats.syntax.monad._

case class Player (name: String)
case class Team (players: List[Player])

// For the sake of example.
def readPlayer: IO[Player] = IO(Player("foo"))

/**
  * Reads a team of 7 players from the command line.
  * @return
  */
def readTeam: IO[Team] = Team(Nil).iterateUntilM(team =>
  readPlayer.map(player => Team(team.players :+ player))
)(_.players.size >= 7)

同样没有显式的递归调用，它甚至比tailRecM版本更具声明性——它只是“迭代地执行这个动作，直到给定的条件成立”。

后记：你可能想知道为什么你曾经使用tailRecMwhen IO#flatMapis stack safe，其中一个原因是你可能有一天决定让你的程序在效果上下文中通用（例如，通过 finally 无标记模式）。在这种情况下，你不应该假设它flatMap的行为方式是你想要的，因为合法性cats.Monad不需要flatMap是堆栈安全的。在这种情况下，最好避免通过flatMap和选择tailRecM或iterateUntilM等显式递归调用，因为这些保证对于任何合法的单子上下文都是堆栈安全的。

于 2019-02-02T12:02:11.263 回答