如何解释Scala Cats / fs2中的堆栈安全性？

Question

这是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
}

Answer 1

我之前的回答在这里提供了一些有用的背景信息。基本思想是某些效果类型具有flatMap直接支持堆栈安全递归的实现-您可以flatMap显式地嵌套调用，也可以根据需要通过递归嵌套调用，而不会嵌套过多。

对于某些效果类型flatMap，由于效果的语义，不可能是堆栈安全的。在其他情况下，可能可以编写堆栈安全的flatMap，但由于性能或其他考虑，实现者可能决定不这样做。

不幸的是，没有标准（甚至是常规的）方法来知道flatMap给定类型的堆栈是否安全。Cats确实包含一项tailRecM操作，该操作应为任何合法的monadic效果类型提供堆栈安全的monadic递归，有时查看tailRecM已知合法的实现可以提供有关a是否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的Monad实例是合法的，这很好地证明了Pull的flatMap是堆栈安全的。在这里一个复杂的因素是，该实例Pull有一个ApplicativeError对约束F是Pull的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实现是合法的。

综上所述：这是一个糟糕的情况，在敏感情况下，您绝对应该编写自己的测试以验证这样的实现是安全的。