在 monad 中工作时如何编写尾递归函数

Question

总的来说，在使用 'inside' monad 时，我在弄清楚如何编写尾递归函数时遇到了问题。这是一个简单的例子：

这是我为了更好地理解 Scala 中的 FP 而编写的一个小示例应用程序。首先提示用户输入由 7 个 Player 组成的 Team。此函数递归读取输入：

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] = ???

现在我想实现的（主要是出于教育目的）是能够在def go(team: Team)前面写一个@tailrec符号。但是我看不到将递归调用作为我的最后一条语句的可能性，因为据我所知，最后一条语句总是必须 'lift' 我的 Team 进入 IO monad。

如有任何提示，我们将不胜感激。

Answer 1

首先，这不是必需的，因为 IO 是专门为支持堆栈安全的单子递归而设计的。来自 the docs:

IO is trampolined in its flatMap evaluation. This means that you can safely call flatMap in a recursive function of arbitrary depth, without fear of blowing the stack…

因此您的实施在堆栈安全方面将工作得很好，即使您需要 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)))
}

这表示 "start with an empty team and repeatedly add players until we have the necessary number"，但没有任何明确的递归调用。只要 monad 实例是合法的（根据 Cats 的定义——有一些关于 tailRecM 是否属于 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 版本更具声明性——它只是 "perform this action iteratively until the given condition holds".

一个后记：您可能想知道为什么在 IO#flatMap 是堆栈安全的情况下使用 tailRecM，一个原因是您可能有一天决定在效果上下文中使您的程序通用（例如，通过 finally 无标签模式）。在这种情况下，您不应该假设 flatMap 会按您希望的方式运行，因为 cats.Monad 的合法性并不要求 flatMap 是堆栈安全的。在那种情况下，最好避免通过 flatMap 进行显式递归调用，而是选择 tailRecM 或 iterateUntilM 等，因为这些保证对于任何合法的单子上下文都是堆栈安全的。

在 monad 中工作时如何编写尾递归函数

How to write tail-recursive functions when working inside monads

io

monads

scala

tail-recursion

cats-effect