scala - 在 monad 内部工作时如何编写尾递归函数

Question

总的来说，我在弄清楚如何在“内部”单子(monad)中工作时编写尾递归函数时遇到问题。这是一个简单的例子:

这是我编写的一个小示例应用程序，旨在更好地理解 Scala 中的 FP。首先，系统会提示用户输入由 7 名玩家组成的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 表示法>。但我不认为有可能将递归调用作为我的最后一条语句，因为据我所知，最后一条语句总是必须将我的Team“提升”到 IO monad 中。

任何提示将不胜感激。

Answer 1

首先，这是没有必要的，因为IO专门设计用于支持堆栈安全的单子(monad)递归。来自 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)))
}

这表示“从一个空团队开始，然后重复添加玩家，直到我们拥有必要的数量”，但没有任何显式的递归调用。只要 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 更具声明性。版本 - 它只是“迭代执行此操作，直到给定条件成立”。

<小时/>

后记:您可能想知道为什么要使用 tailRecM当IO#flatMap是堆栈安全的，原因之一是您有一天可能决定使您的程序在效果上下文中通用(例如通过finally tagless模式)。在这种情况下，您不应假设 flatMap行为如您所愿，因为 cats.Monad 的合法性不需要flatMap为了堆栈安全。在这种情况下，最好避免通过 flatMap 进行显式递归调用。并选择tailRecM或iterateUntilM等，因为这些保证对于任何合法的单子(monad)上下文都是堆栈安全的。