Why scala @tailrec can't be used on Option.flatMap?

Question

In scala, the following 2 functions serve exactly the same purpose:

@tailrec
final def fn(str: String): Option[String] = {
  Option(str).filter(_.nonEmpty).flatMap { v =>
    fn(v.drop(1))
  }
}

@tailrec
final def fn2(str: String): Option[String] = {
  Option(str).filter(_.nonEmpty) match {
    case None    => None
    case Some(v) => fn2(v.drop(1))
  }
}

However @tailrec only works in second case, in the first case it will generate the following error:

Error: could not optimize @tailrec annotated method fn: it contains a recursive call not in tail position Option(str).filter(_.nonEmpty).flatMap { v =>

Why this error was given? And why these 2 codes generate different kinds JVM bytecode

Answer 1

Consider the following:

List('a', 'b').flatMap(List(_,'g'))  //res0: List[Char] = List(a, g, b, g)

I seems pretty obvious that flatMap() is doing some internal post-processing in order to achieve that result. How else would List('a','g') get combined with List('b','g')?

Answer 2

For fn to be tail-recursive, the recursive call must be the last action in the function. If you pass fn to another function such as flatMap then the other function is free to perform other actions after calling fn and therefore the compiler cannot be sure that it is tail recursive.

In some cases the compiler could detect that calling fn is the last action in the other function, but not in the general case. And this would rely on a specific implementation of that other function so the tailrec annotation might become invalid if that other function were changed, which is an undesirable dependency.

Answer 3

Specifically for the last question:

And why these 2 codes generate different kinds JVM bytecode

Because on JVM there's no guarantee that the JAR containing Option class at runtime is the same as was seen at compile-time. This is good, because otherwise even minor versions of libraries (including standard Java and Scala libraries) would be incompatible, and you'd need all dependencies to be using the same minor version of their common dependencies.

If that class doesn't have a suitable flatMap method, you'll get AbstractMethodError, but otherwise semantics of Scala require that its flatMap method must be called. So the compiler has to emit bytecode to actually call the method.

Kotlin works around this by using inline functions and Scala 3 will support them too, but I don't know if it'll use them for such cases.