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

Question

一般来说,我在查找如何在"内部"monad中编写tailrecursive函数时遇到问题.这是一个简单的例子:

这是我写的一个小示例应用程序,以更好地理解Scala中的FP.首先,提示用户进入由7名玩家组成的团队.此函数以递归方式读取输入:

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).但是我没有看到将递归调用作为我的最后一个声明的可能性,因为就我所见,最后一个声明总是必须"解除"我的团队进入IO monad.

任何暗示都将非常感激.

Answer 1

首先,这不是必需的,因为它IO是专门为支持堆栈安全的monadic递归而设计的.来自文档:

IO在flatMap评估中受到贬低.这意味着你可以安全地调用flatMap任意深度的递归函数,而不用担心会烧掉堆栈......

所以你的实现在堆栈安全性方面可以正常工作,即使不是七个玩家你需要70,000个玩家(尽管那时你可能需要担心堆).

然而,这并没有真正回答你的问题,当然,即使@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无标记模式).在这种情况下,您不应该假设flatMap行为符合您的预期,因为合法性cats.Monad不需要flatMap堆栈安全.在这种情况下,这将是最好的,以避免通过明确的递归调用flatMap和选择tailRecM或iterateUntilM替代,等等,因为这些都保证了任何合法单子背景下堆栈安全.