Jak uzasadnić bezpieczeństwo stosu w Scala Cats / fs2?

Oto fragment kodu z dokumentacji dla fs2 . Funkcja gojest rekurencyjna. Pytanie brzmi: skąd wiemy, czy można je bezpiecznie nakładać i jak uzasadnić, czy jakakolwiek funkcja jest bezpieczna w stosie?

import fs2._
// import fs2._

def tk[F[_],O](n: Long): Pipe[F,O,O] = {
  def go(s: Stream[F,O], n: Long): Pull[F,O,Unit] = {
    s.pull.uncons.flatMap {
      case Some((hd,tl)) =>
        hd.size match {
          case m if m <= n => Pull.output(hd) >> go(tl, n - m)
          case m => Pull.output(hd.take(n.toInt)) >> Pull.done
        }
      case None => Pull.done
    }
  }
  in => go(in,n).stream
}
// tk: [F[_], O](n: Long)fs2.Pipe[F,O,O]

Stream(1,2,3,4).through(tk(2)).toList
// res33: List[Int] = List(1, 2)

Czy byłoby również bezpieczne w stosie, gdybyśmy zadzwonili goz innej metody?

def tk[F[_],O](n: Long): Pipe[F,O,O] = {
  def go(s: Stream[F,O], n: Long): Pull[F,O,Unit] = {
    s.pull.uncons.flatMap {
      case Some((hd,tl)) =>
        hd.size match {
          case m if m <= n => otherMethod(...)
          case m => Pull.output(hd.take(n.toInt)) >> Pull.done
        }
      case None => Pull.done
    }
  }

  def otherMethod(...) = {
    Pull.output(hd) >> go(tl, n - m)
  }

  in => go(in,n).stream
}

Moja poprzednia odpowiedź tutaj zawiera pewne podstawowe informacje, które mogą być przydatne. Podstawową ideą jest to, że niektóre typy efektów mają flatMapimplementacje, które bezpośrednio obsługują rekurencję bezpieczną dla stosu - możesz zagnieżdżać flatMappołączenia jawnie lub poprzez rekurencję tak głęboko, jak chcesz, i nie przepełnisz stosu.

W przypadku niektórych typów efektów nie jest możliwe flatMapzachowanie bezpiecznego stosu, ze względu na semantykę efektu. W innych przypadkach może być możliwe napisanie bezpiecznego dla stosu flatMap, ale implementatorzy mogliby tego nie robić z powodu wydajności lub innych czynników.

Niestety nie ma standardowego (ani nawet konwencjonalnego) sposobu na sprawdzenie, czy flatMapdany typ jest bezpieczny dla stosów. Koty zawierają tailRecMoperację, która powinna zapewnić bezpieczną dla stosu rekurencję monadyczną dla dowolnego zgodnego z prawem typu efektu monadycznego, a czasem spojrzenie na tailRecMimplementację, o której wiadomo, że jest zgodna z prawem, może dostarczyć pewnych wskazówek na temat tego, czy flatMapmożna bezpiecznie stosować stos. W przypadku Pullwygląda na to, to :

def tailRecM[A, B](a: A)(f: A => Pull[F, O, Either[A, B]]) =
  f(a).flatMap {
    case Left(a)  => tailRecM(a)(f)
    case Right(b) => Pull.pure(b)
  }

To tailRecMwłaśnie dzięki recursing flatMap, i wiemy, że Pulljest Monadinstancja jest zgodne z prawem , co jest bardzo dobrym dowodem, że Pull's flatMapznaczy stos bezpieczny. Ten, komplikując czynnikiem jest to, że na przykład Pullma ApplicativeErrorograniczenie na Fto Pull„s flatMapnie, ale w tym przypadku to nie zmienia niczego.

Tak więc tkimplementacja jest bezpieczna dla stosu, ponieważ flatMapon Pulljest bezpieczny dla stosu, i wiemy to po spojrzeniu na jego tailRecMimplementację. (Jeśli wykopali głębiej możemy dowiedzieć się, że flatMapjest bezpieczny, ponieważ stos Pulljest zasadniczo otoki dla FreeC, których jest trampolined ).

Prawdopodobnie nie byłoby strasznie trudne do przerobienia tkw kategoriach tailRecM, choć musielibyśmy dodać inaczej niepotrzebne ApplicativeErrorograniczenie. Zgaduję, że autorzy dokumentacji postanowili nie robić tego dla jasności, a ponieważ wiedzieli Pull, że flatMapjest w porządku.

Aktualizacja: oto dość mechaniczne tailRecMtłumaczenie:

import cats.ApplicativeError
import fs2._

def tk[F[_], O](n: Long)(implicit F: ApplicativeError[F, Throwable]): Pipe[F, O, O] =
  in => Pull.syncInstance[F, O].tailRecM((in, n)) {
    case (s, n) => s.pull.uncons.flatMap {
      case Some((hd, tl)) =>
        hd.size match {
          case m if m <= n => Pull.output(hd).as(Left((tl, n - m)))
          case m => Pull.output(hd.take(n.toInt)).as(Right(()))
        }
      case None => Pull.pure(Right(()))
    }
  }.stream

Pamiętaj, że nie ma wyraźnej rekurencji.

Odpowiedź na twoje drugie pytanie zależy od tego, jak wygląda druga metoda, ale w przypadku twojego konkretnego przykładu, >>po prostu spowoduje więcej flatMapwarstw, więc powinno być dobrze.

Aby odpowiedzieć bardziej ogólnie na twoje pytanie, cały ten temat jest mylącym bałaganem w Scali. Nie powinieneś zagłębiać się w implementacje, jak to zrobiliśmy powyżej, tylko po to, aby wiedzieć, czy typ obsługuje bezpieczną rekurencję monadyczną, czy nie. Pomocne byłyby lepsze konwencje dotyczące dokumentacji, ale niestety nie robimy tego zbyt dobrze. Zawsze możesz tailRecMbyć „bezpieczny” (co F[_]zresztą chcesz zrobić, gdy jest to ogólne), ale nawet wtedy ufasz, że Monadwdrożenie jest zgodne z prawem.

Podsumowując: ogólnie jest to zła sytuacja, aw delikatnych sytuacjach zdecydowanie powinieneś napisać własne testy, aby sprawdzić, czy takie implementacje są bezpieczne dla stosów.