13

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

1 回答 1

18

我之前的回答在这里提供了一些可能有用的背景信息。基本思想是某些效果类型具有flatMap直接支持堆栈安全递归的实现——您可以flatMap显式嵌套调用，也可以通过递归任意深度嵌套调用，并且不会溢出堆栈。

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

不幸的是，没有标准（甚至是传统的）方法可以知道flatMap给定类型的 是否是堆栈安全的。Cats 确实包含一个tailRecM操作，该操作应该为任何合法的单子效果类型提供堆栈安全的单子递归，有时查看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是堆栈安全的。这里的一个复杂因素是实例 forPull对's没有ApplicativeError约束F，但在这种情况下不会改变任何东西。PullflatMap

所以tk这里的实现是栈安全的，因为flatMaponPull是栈安全的，我们通过查看它的tailRecM实现就知道了。（如果我们再深入一点，我们可以发现它flatMap是堆栈安全的，因为Pull它本质上是 的包装器FreeC，它是蹦床的。）

尽管我们必须添加其他不必要的约束，但tk用来重写可能并不难。我猜文档的作者为了清楚起见选择不这样做，因为他们知道's很好。tailRecMApplicativeErrorPullflatMap

更新：这是一个相当机械的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实施是合法的。

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

于 2019-11-28T08:49:14.500 回答