Jak pisać funkcje rekurencyjne podczas pracy wewnątrz monad

Question

Jak pisać funkcje rekurencyjne podczas pracy wewnątrz monad

Ogólnie mam problemy z wymyśleniem, jak pisać funkcje tailrecursywne podczas pracy' wewnątrz ' monad. Oto krótki przykład:

To jest z małej przykładowej aplikacji, którą piszę, aby lepiej zrozumieć FP w Scali. Po pierwsze użytkownik jest proszony o wprowadzenie Team składającej się z 7 Players. Ta funkcja rekurencyjnie odczytuje wejście:

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] = ???

Teraz to, co chciałbym osiągnąć (głównie w celach edukacyjnych), to móc napisać @tailrec zapis przed def go(team: Team). Ale nie widzę możliwości, aby wywołanie rekurencyjne było moim ostatnim stwierdzeniem, ponieważ ostatnie stwierdzenie, o ile widzę, zawsze musi "podnieść" moje Team do monady IO.

Każda podpowiedź byłaby bardzo mile widziana.

18

io tail-recursion monads scala cats-effect

Author: Florian Baierl, 2019-02-02

Source

1 answers

score 24 · Accepted Answer

Po pierwsze, nie jest to konieczne, ponieważ IO jest specjalnie zaprojektowany do obsługi bezpiecznej dla stosu rekurencji monadycznej. Z docs :

IO jest trampoliną w swojej ocenie flatMap. Oznacza to, że można bezpiecznie wywołać flatMap w funkcji rekurencyjnej o dowolnej głębokości, bez obawy o wysadzenie stosu...

Więc twoja implementacja będzie działać dobrze pod względem bezpieczeństwa stosu, nawet jeśli zamiast siedmiu graczy potrzebujesz 70 000 graczy (chociaż w tym momencie możesz potrzebować martwić się o stertę).

To tak naprawdę nie odpowiada na twoje pytanie i oczywiście nawet @tailrec nigdy nie jest konieczne , ponieważ wszystko, co robi, to sprawdza, czy kompilator robi to, co myślisz, że powinien robić.

Chociaż nie jest możliwe napisanie tej metody w taki sposób, aby można było ją przypisać @tailrec, można uzyskać podobny rodzaj pewności używając Cats ' s tailRecM. Na przykład, następujące są równoważne z Twoim realizacja:

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)))
}

To mówi: "zacznij od pustej drużyny i wielokrotnie dodawaj graczy, dopóki nie będziemy mieli wymaganego numeru", ale bez wyraźnych wywołań rekurencyjnych. Dopóki instancja monad jest zgodna z prawem (zgodnie z definicją Cats-jest pytanie, czy tailRecM w ogóle należy do Monad), nie musisz się martwić o bezpieczeństwo stosu.

Na marginesie, fa.as(b) jest równoważne fa >>= (_ => IO(b)), ale bardziej idiomatyczne.

Również na marginesie (ale może bardziej ciekawe), można napisać tę metodę jeszcze bardziej zwięźle (i na moje oko wyraźniej) w następujący sposó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)

Ponownie nie ma jawnych wywołań rekurencyjnych, a jest to nawet bardziej deklaratywne niż wersja tailRecM-po prostu "wykonaj tę akcję iteracyjnie, aż dany warunek się utrzyma".

Jeden postscript: możesz się zastanawiać, dlaczego kiedykolwiek używasz tailRecM, Gdy IO#flatMap jest bezpieczny dla stosu, a jednym z powodów jest to, że pewnego dnia możesz zdecydować się na ogólny program w efekcie kontekstu (np. poprzez wzorzec finally tagless). W tym przypadku nie powinieneś zakładać, że flatMap zachowuje się tak, jak chcesz, ponieważ legalność dla {[17] }nie wymaga, aby flatMap było bezpieczne dla stosu. W takim przypadku najlepiej byłoby unikać jawnych wywołań rekurencyjnych poprzez flatMap i wybrać tailRecM lub iterateUntilM, itd. zamiast tego, ponieważ są one gwarantowane, że będą bezpieczne dla dowolnego zgodnego z prawem kontekstu monadycznego.