Как писать хвостовые рекурсивные функции при работе внутри монад

Question

Вообще у меня проблемы с выяснением того, как писать хвостовые рекурсивные функции при работе "внутри" монад. Вот быстрый пример:

Это из небольшого примера приложения, которое я пишу, чтобы лучше понять FP в Scala. Прежде всего пользователю предлагается ввести команду, состоящую из 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), Но я не вижу возможности использовать рекурсивный вызов в качестве моего последнего утверждения, поскольку, насколько я вижу, последнее утверждение всегда должно "поднять" мою команду в монаду ввода-вывода.

Любая подсказка будет принята с благодарностью.

Answer 1

Прежде всего, это не обязательно, потому что IO специально разработан для поддержки монадической рекурсии в стеке Из документов:

IO батут в его flatMap оценка. Это означает, что вы можете безопасно позвонить flatMap в рекурсивной функции произвольной глубины, не боясь взорвать стек...

Таким образом, ваша реализация будет работать нормально с точки зрения безопасности стека, даже если вместо семи игроков вам понадобится 70000 игроков (хотя в этот момент вам, возможно, придется беспокоиться о куче).

Это на самом деле не отвечает на ваш вопрос, и, конечно, даже @tailrec в этом нет необходимости, поскольку все, что он делает, это проверяет, что компилятор делает то, что, как вы думаете, он должен делать.

Хотя невозможно написать этот метод таким образом, чтобы его можно было @tailrec, вы можете получить аналогичный вид гарантии, используя кошки 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 является безопасным для стека, и одна из причин заключается в том, что вы можете однажды решить сделать свою программу универсальной в контексте эффекта (например, с помощью шаблона, наконец, без тегов). В этом случае вы не должны предполагать, что flatMap ведет себя так, как вы хотите, так как законность для cats.Monad не требует flatMap быть в безопасности В этом случае было бы лучше избегать явных рекурсивных вызовов через flatMap и выбрать tailRecM или же iterateUntilMи т. д., поскольку они гарантированно безопасны для любого законного монадического контекста.