在monad内部工作时如何编写尾递归函数 [英] How to write tail-recursive functions when working inside monads

问题描述

总的来说，当在内部" monad中工作时，我很难弄清楚如何编写tailrecursive函数.这是一个简单的示例:

In general I have problems figuring out how to write tailrecursive functions when working 'inside' monads. Here is a quick example:

这来自我正在编写的一个小示例应用程序，目的是更好地了解Scala中的FP.首先，提示用户输入由7个Player组成的Team.此函数以递归方式读取输入:

This is from a small example application that I am writing to better understand FP in Scala. First of all the user is prompted to enter a Team consisting of 7 Players. This function recursively reads the input:

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中.

Now what I'd like to achieve (mainly for educational purposes) is to be able to write a @tailrec notation in front of def go(team: Team). But I don't see a possibility to have the recursive call as my last statement because the last statement as far as I can see always has to 'lift' my Team into the IO monad.

任何提示将不胜感激.

推荐答案

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

First of all, this isn't necessary, because IO is specifically designed to support stack-safe monadic recursion. From the docs:

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

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…

因此，就堆栈安全而言，即使您需要7万名玩家(而不是7名玩家)，您的实现也可以正常工作(尽管此时您可能需要担心堆).

So your implementation will work just fine in terms of stack safety, even if instead of seven players you needed 70,000 players (although at that point you might need to worry about the heap).

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

This doesn't really answer your question, though, and of course even @tailrec is never necessary, since all it does is verify that the compiler is doing what you think it should be doing.

虽然无法以可以用@tailrec进行注释的方式编写此方法，但是可以通过使用Cats的tailRecM获得类似的保证.例如，以下等同于您的实现:

While it's not possible to write this method in such a way that it can be annotated with @tailrec, you can get a similar kind of assurance by using Cats's tailRecM. For example, the following is equivalent to your implementation:

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都有疑问)，您不必担心堆栈安全性.

This says "start with an empty team and repeatedly add players until we have the necessary number", but without any explicit recursive calls. As long as the monad instance is lawful (according to Cats's definition—there's some question about whether tailRecM even belongs on Monad), you don't have to worry about stack safety.

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

As a side note, fa.as(b) is equivalent to fa >>= (_ => IO(b)) but more idiomatic.

作为附带说明(但也许更有趣)，您可以更简洁地编写此方法(对我而言更清晰)，如下所示:

Also as a side note (but maybe a more interesting one), you can write this method even more concisely (and to my eye more clearly) as follows:

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版本更具声明性，它只是迭代执行此操作，直到给定条件成立".

Again there are no explicit recursive calls, and it's even more declarative than the tailRecM version—it's just "perform this action iteratively until the given condition holds".

一个后记:您可能想知道为什么IO#flatMap在堆栈安全的情况下会使用tailRecM，原因之一是您可能有一天可能决定使程序在效果上下文中具有通用性(例如，通过最终的无标记)图案).在这种情况下，您不应该假定flatMap的行为符合您的期望，因为cats.Monad的合法性并不要求flatMap是堆栈安全的.在那种情况下，最好避免通过flatMap进行显式的递归调用，而选择tailRecM或iterateUntilM等，因为这样可以保证对于任何合法的单子上下文都是安全的.

One postscript: you might wonder why you'd ever use tailRecM when IO#flatMap is stack safe, and one reason is that you may someday decide to make your program generic in the effect context (e.g. via the finally tagless pattern). In this case you should not assume that flatMap behaves the way you want it to, since lawfulness for cats.Monad doesn't require flatMap to be stack safe. In that case it would be best to avoid explicit recursive calls through flatMap and choose tailRecM or iterateUntilM, etc. instead, since these are guaranteed to be stack safe for any lawful monadic context.

这篇关于在monad内部工作时如何编写尾递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！