scala - 如何推理 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

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

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

不幸的是，没有标准(甚至传统)方法来知道给定类型的 flatMap 是否是堆栈安全的。 Cats 确实包含一个 tailRecM 操作，该操作应该为任何合法的单子(monad)效果类型提供堆栈安全的单子(monad)递归，有时查看已知合法的 tailRecM 实现可以提供一些有关 flatMap 是否堆栈安全的提示。在 Pull 的情况下，它看起来像 this :

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实例is lawful，这是很好的证据，证明 Pull 的 flatMap 是堆栈安全的。这里的一个复杂因素是 Pull 的实例对 F 有一个 ApplicativeError 约束，Pull 的 flatMap 不会，但在这种情况下不会改变任何东西。

所以这里的 tk 实现是堆栈安全的，因为 Pull 上的 flatMap 是堆栈安全的，并且我们通过查看其tailRecM 实现。 (如果我们深入挖掘，我们可以发现 flatMap 是堆栈安全的，因为 Pull 本质上是 FreeC 的包装器，即 trampolined .)

用 tailRecM 重写 tk 可能不会太难，尽管我们必须添加原本不必要的 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 中都是一团困惑。您不必像我们上面那样深入研究实现，只是为了知道类型是否支持堆栈安全的单子(monad)递归。更好的文档约定在这里会有所帮助，但不幸的是我们在这方面做得并不好。您始终可以使用 tailRecM 来确保“安全”(无论如何，当 F[_] 是通用的时，您会想要这样做)，但即便如此，您相信 Monad 实现是合法的。

总而言之:这是一个糟糕的情况，在敏感情况下，您绝对应该编写自己的测试来验证这样的实现是否是堆栈安全的。