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

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?

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))

The issue is similar to question Scala @tailrec with fold, but here I'd like to find out why and whether this could be supported in the future.

The example is for Scala 3.1, but the issue itself is valid for Scala 2.x as well.

Solution 1:

The recursive call happens inside a lambda. So it is not a tail recursive call unless the compiler would inline the fold and the lambda into your own method and only then test whether it is tail recursive. However the compiler does not do that automatically and it probably never will do that automatically.

The good news is that in Scala 3 you can pretty easily work around that, and it is theoretically possible that the standard library will ever be adapted to take advantage of that. All it takes is explicitly implementing fold as an inline method with inline parameters.

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))

Note that an inline parameter automatically has by-name semantics, so onEmpty is already by-name without changing the type to => B.

Solution 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?

This is simply the definition of tail recursion. A tail call is the last call in a subroutine. Recursion is when a subroutine calls itself. Tail recursion is when the tail call is a recursive call, or when the recursive call is in tail position – in other words, it is when a subroutine calls itself as the last call.

In your case, the last call is to fold, not to sumAllFold.

This is not a shortcoming of the Scala compiler or of the Scala library. sumAllFold isn't tail recursive, because its tail call is not the recursive call and the recursive call is not the tail call. In other words, it is not tail recursive, because it simply is not tail recursive.

This is basically the same as asking whether it is a shortcoming of your mechanic that your blue car isn't yellow. It is not. Your blue car isn't yellow because it simply isn't.