代码之家  ›  专栏  ›  技术社区  ›  Florian Baierl

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

  •  12
  • Florian Baierl  · 技术社区  · 7 年前

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

    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) . 但我不认为有可能将递归调用作为我的最后一条语句,因为我所能看到的最后一条语句总是要“提升”我的 团队 进入了木卫一。

    任何暗示都将不胜感激。

    1 回复  |  直到 6 年前
        1
  •  26
  •   Travis Brown    7 年前

    首先,这是没有必要的,因为 IO 是专门为支持堆栈安全的单元递归而设计的。从…起 the docs :

    木卫一 flatMap 评价这意味着您可以安全地拨打电话 平面图 在任意深度的递归函数中,无需担心堆栈被吹走

    但这并不能真正回答你的问题,当然,甚至 @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)))
    }
    

    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 是堆栈安全的,其中一个原因是有一天您可能会决定在effect上下文中使程序通用(例如,通过finally-tagless模式)。在这种情况下,你不应该假设 按照你希望的方式行事,因为 cats.Monad 平面图 为了安全起见。在这种情况下,最好避免通过 选择 tailRecM 或 iterateUntilM ,等等,因为它们保证在任何合法的一元上下文中都是堆栈安全的。