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

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

0 голосов
/ 02 февраля 2019

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

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

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

1 Ответ

0 голосов
/ 02 февраля 2019

Прежде всего, в этом нет необходимости, потому что 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)))
}

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

...