Como raciocinar sobre a segurança da pilha no Scala Cats / fs2?

Aqui está um pedaço de código da documentação para fs2 . A função goé recursiva. A questão é: como sabemos se a pilha é segura e como raciocinar se alguma função é segura?

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)

Também seria seguro para a pilha se chamarmos gode outro método?

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
}

Minha resposta anterior aqui fornece algumas informações básicas que podem ser úteis. A idéia básica é que alguns tipos de efeito tenham flatMapimplementações que suportam diretamente a recursão segura para a pilha - você pode aninhar flatMapchamadas explicitamente ou por recursão tão profundamente quanto desejar e não excederá a pilha.

Para alguns tipos de efeito, não é possível flatMapter segurança na pilha, devido à semântica do efeito. Em outros casos, pode ser possível escrever um cofre de pilha flatMap, mas os implementadores podem ter decidido não fazê-lo por causa do desempenho ou de outras considerações.

Infelizmente, não existe uma maneira padrão (ou mesmo convencional) de saber se o flatMaptipo de dado é seguro para a pilha. Cats inclui uma tailRecMoperação que deve fornecer recursão monádica segura para qualquer tipo de efeito monádico legal e, às vezes, observar uma tailRecMimplementação que seja legal pode fornecer algumas dicas sobre se a flatMappilha é segura. No caso de Pullele se parece com isso :

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

Esta tailRecMé apenas recursão através flatMap, e nós sabemos que Pull's Monadexemplo é lícito , o que é bastante boa evidência de que Pull' s flatMapé pilha-safe. O único complicador aqui é que a instância para que Pulltem uma ApplicativeErrorrestrição sobre Fque Pull's flatMapnão, mas neste caso isso não muda nada.

Portanto, a tkimplementação aqui é segura para a pilha, porque flatMapon Pullé segura para a pilha, e sabemos disso ao analisar sua tailRecMimplementação. (Se aprofundarmos um pouco mais, poderemos descobrir que flatMapé seguro para a pilha, porque Pullé essencialmente um invólucro FreeC, que é trampolim .)

Provavelmente não seria terrivelmente difícil reescrever tkem termos de tailRecM, embora tenhamos que adicionar a ApplicativeErrorrestrição desnecessária . Eu estou supondo que os autores da documentação escolheu não fazer isso para maior clareza, e porque sabiam Pullé flatMapestá bem.

Atualização: aqui está uma tailRecMtradução bastante mecânica :

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

Observe que não há recursão explícita.

A resposta para sua segunda pergunta depende da aparência do outro método, mas, no caso de seu exemplo específico, >>resultará apenas em mais flatMapcamadas, portanto tudo ficará bem.

Para responder à sua pergunta de maneira mais geral, todo esse tópico é uma bagunça confusa no Scala. Você não precisa se aprofundar nas implementações, como fizemos acima, apenas para saber se um tipo suporta recursão monádica segura para pilha ou não. Melhores convenções sobre documentação seriam uma ajuda aqui, mas infelizmente não estamos fazendo um bom trabalho nisso. Você sempre pode tailRecMser "seguro" (que é o que você deseja fazer quando F[_]for genérico, de qualquer maneira), mas mesmo assim você confia que a Monadimplementação é legal.

Resumindo: é uma situação ruim e, em situações sensíveis, você definitivamente deve escrever seus próprios testes para verificar se implementações como essa são seguras para a pilha.