Как рассуждать о безопасности стека в Scala Cats / fs2?

Вот фрагмент кода из документации для fs2 . Функция goрекурсивная. Вопрос в том, как узнать, безопасен ли он для стека, и как определить, является ли какая-либо функция безопасной для стека?

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)

Будет ли это также безопасно для стека, если мы вызовем goдругой метод?

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
}

Мой предыдущий ответ здесь дает некоторую справочную информацию , которая может оказаться полезной. Основная идея заключается в том, что некоторые типы эффектов имеют flatMapреализации, которые поддерживают рекурсию, безопасную для стека, - вы можете вкладывать flatMapвызовы либо явно, либо через рекурсию настолько глубоко, насколько захотите, и вы не переполните стек.

Для некоторых типов эффектов невозможно flatMapобеспечить безопасность стека из-за семантики эффекта. В других случаях может быть возможно написать безопасный для стека flatMap, но разработчики, возможно, решили не делать этого из-за производительности или других соображений.

К сожалению, не существует стандартного (или даже обычного) способа узнать, является ли flatMapдля данного типа стек-безопасным. Cats включает в себя tailRecMоперацию, которая должна обеспечить безопасную для стека монадическую рекурсию для любого законного монадического типа эффекта, и иногда рассмотрение tailRecMреализации, которая, как известно, является законной, может дать некоторые подсказки о том, является ли объект flatMapбезопасным для стека. В случае Pullэто выглядит как это :

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

Это tailRecMпросто рекурсии через flatMap, и мы знаем , что Pull«s Monadэкземпляр является законным , что является довольно хорошим доказательством того, что Pull» s flatMapесть стек-сейф. Один осложняющий фактор здесь является то , что экземпляр для Pullимеет ApplicativeErrorограничение на Fтом , что Pull«s flatMapне делает, но в данном случае это не меняет ничего.

Таким образом, tkреализация здесь безопасна для стека, потому что flatMapon безопасна для Pullстека, и мы знаем это по ее tailRecMреализации. (Если бы мы копали немного глубже, мы могли бы выяснить, что flatMapэто безопасно для стека, потому что Pullэто, по сути, обертка для FreeC, которая трамплина .)

Вероятно, было бы не очень сложно переписать tkс точки зрения tailRecM, хотя мы должны были бы добавить иное ненужное ApplicativeErrorограничение. Я предполагаю, что авторы документации решили не делать этого для ясности, и потому что они знали, Pullчто flatMapвсе в порядке.

Обновление: вот довольно механический tailRecMперевод:

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

Обратите внимание, что нет явной рекурсии.

Ответ на ваш второй вопрос зависит от того, как выглядит другой метод, но в случае с вашим конкретным примером >>это приведет к большему количеству flatMapслоев, так что все должно быть в порядке.

Чтобы ответить на ваш вопрос в более общем плане, вся эта тема - запутанный беспорядок в Scala. Вам не нужно копаться в реализациях, как мы делали выше, просто чтобы узнать, поддерживает ли тип монадическую рекурсию, ориентированную на стек, или нет. Здесь лучше помогли бы соглашения о документации, но, к сожалению, мы не очень хорошо справляемся с этим. Вы всегда можете использовать, tailRecMчтобы быть «безопасным» (это то, что вы захотите делать, когда F[_], в любом случае, оно является универсальным), но даже тогда вы верите, что Monadреализация законна.

Подводя итог: это плохая ситуация, и в чувствительных ситуациях вы должны обязательно написать свои собственные тесты, чтобы убедиться, что подобные реализации безопасны для стека.