Tailrec support for Option.fold

Scala Standard Library
#1

With the current implementation of Option.fold (as seen when looking in Scala 3.1)

@inline final def fold[B](ifEmpty: => B)(f: A => B): B =
  if (isEmpty) ifEmpty else f(this.get)

the following (silly) example is not tail recursive:

def recurse(in: Int): Int =
  Option(1).fold(1)(next => recurse(in + 1))

If we would change the standard library to implement Option.fold like this:

inline final def fold[B](inline ifEmpty: B)(inline f: A => B): B =
  if (isEmpty) ifEmpty else f(this.get)

then the same example is tailrec. Is this something that has a chance to be accepted in the scala/scala-library-next repository? I’m willing to create a PR, but first would like to check whether it has chances to be accepted…

See also Why can’t Option.fold be used tail recursively in Scala? - Stack Overflow

5 Likes
#2

.fold(ifEmpty)(f) is equivalent to .map(f).getOrElse(ifEmpty).

It would be strange, if one is tailrec while other is not. Then we would need to add inline to .map parameter.

…but .map itself is equivalent to .flatMap(a => Some(f(a))) and so it continues…

#3

Scala 2 -optimize (which means inline everything possible) does inline the call, but tailcalls is a phase that runs relatively early.

The optimizer could apply or re-apply the optimization after inlining. (It could do that under a flag, where -opt:tailcalls enables aggressive optimizing only for annotated methods, that is, annotated methods which were not already tail-recursive.)

If I may be permitted to abuse the idiom, the question that should not go begging is whether we should worry about it.

Scala 3’s inline is a bit different because it enforces certain semantics.

But @tailrec and @inline are just tools for inspecting or verifying what code is emitted. Maybe we want better tools for linting byte code. It’s tiresome to break out javap just to check that a value isn’t boxed, for example.

The tooling should tell me when my optimization is not premature. For example, my only signal that a method consumes a lot of stack is when it runs out of stack. Nothing warns me that my test suite just barely scrapes by but in production will probably SOE. Possibly we are more likely to probe heap usage during testing and tune accordingly. But I’d like to know if my unoptimized fold is good enough for my anticipated production data, or if -opt:tailcalls worked for me.

In the absence of tooling, I wind up adding @tailrec, probably in the same commit I tweak indentation and either add or remove braces.

2 Likes
#4

Hello!
Unfortunately, scala-library-next can not change the signature of existing methods.
In this case, the workaround is to rewrite recurse with pattern matching instead of fold:

def recurse(in: Int): Int =
  Option(1) match { case Nil => 1 case Some(next) => recurse(in + 1) }
#5

Thanks, just what I wanted to know! This saves me from the effort of creating a useless PR to scala-library-next. (Although I would have liked to see Option.fold become tailrec-enabled…)