为什么不能在 Scala 中递归地使用 Option.fold？

Question

下面，sumAllIf是尾递归而sumAllFold不是。但是，sumAllIf 实际上具有相同的实现。这是 Scala 编译器（或 Scala 库）的缺点，还是我忽略了什么？

def maybeNext(in: Int): Option[Int] = if in < 10 then Some(in + 1) else None

// The Scala library implements Option.fold like this:
// @inline final def fold[B](ifEmpty: => B)(f: A => B): B =
//   if (isEmpty) ifEmpty else f(this.get)
@annotation.tailrec
def sumAllIf(current: Int, until: Int, sum: Int): Int =
  val nextOption = maybeNext(current)
  if (nextOption.isEmpty) sum else sumAllIf(nextOption.get, until, sum + nextOption.get)

// However, with Scala 3.1.0 and earlier, this is NOT tail recursive:
def sumAllFold(current: Int, until: Int, sum: Int): Int =
  maybeNext(current).fold(sum)(next => sumAllFold(next, until, sum + next))

@main def main(): Unit =
  println(sumAllIf(0, 10, 0))
  println(sumAllFold(0, 10, 0))

这个问题和问题类似，但是这里我想知道为什么以及这个是否可以 以后会支持的。

该示例适用于 Scala 3.1，但问题本身也适用于 Scala 2.x。

Answer 1

递归调用发生在 lambda 内部。所以它不是尾递归调用，除非编译器将折叠和 lambda 内联到您自己的方法中，然后才测试它是否是尾递归。但是，编译器不会自动执行此操作，而且它可能永远不会自动执行此操作。

好消息是，在 Scala 3 中，您可以很容易地解决这个问题，而且从理论上讲，标准库有可能会进行调整以利用它。它所要做的就是明确地将 fold 实现为具有内联参数的内联方法。

inline def fold[A, B](opt: Option[A])(inline onEmpty: B)(inline f: A => B): B =
  opt match
    case Some(a) => f(a)
    case None => onEmpty

@annotation.tailrec
def sumAllFold(current: Int, until: Int, sum: Int): Int =
  fold(maybeNext(current))(sum)(next => sumAllFold(next, until, sum + next))

请注意，内联参数自动具有 by-name 语义，因此 onEmpty 已经是 by-name 而无需将类型更改为 => B。

Answer 2

Below, sumAllIf is tail recursive and sumAllFold is not. However, sumAllIf effectively has the same implementation. Is this a shortcoming of the Scala compiler (or of the Scala library), or am I overlooking something?

这就是尾递归的简单定义。 尾调用 是子例程中的最后一次调用。递归是子程序调用自身的时候。 尾递归是当尾调用是递归调用，或者当递归调用在尾位置时——换句话说，当子程序调用自身作为最后调用时。

在您的情况下，最后一次调用是 fold，而不是 sumAllFold。

这不是 Scala 编译器或 Scala 库的缺点。 sumAllFold 不是尾递归，因为它的尾调用不是递归调用，递归调用也不是尾调用。换句话说，它不是尾递归，因为它根本就不是尾递归。

这与询问您的蓝色汽车不是黄色是否是您的机械师的缺点基本相同。它不是。你的蓝色车不是黄色的，因为它根本不是。

为什么不能在 Scala 中递归地使用 Option.fold？

Why can't Option.fold be used tail recursively in Scala?

scala

tail-recursion

fold