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

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 @tailrec with Fold，但在这里我想找出原因以及将来是否可以支持。

该示例适用于 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))

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