Open Atry opened 7 years ago
@Atry Your last
method is not tail recursive. (Hint: cons.last()
is not the same as last()
)
I guess the error here is in the error message. Should be:
<console>:18: error: could not optimize @tailrec annotated method last: it contains a recursive call not in tail position
cons.last()
^
instead of:
<console>:20: error: could not optimize @tailrec annotated method last: it contains a recursive call not in tail position
notCons
^
@jvican That's an assessment I'd second.
Shouldn't the error rather be
@tailrec annotated method contains no recursive calls
when aiming low, or something like
@tailrec annotated method contains no recursive calls
because
`last` on `cons` is not the same function as `last` on `this`
when aiming high?
scalac is in general perfectly capable of tailrec-transforming methods that call themselves on a different receiver than this
. However, it cannot do so if the polymorphic type of this
changes. The compile error I would expect in this case should be similar to what we get with an if
instead of the match
:
scala> trait Cons[A] {
| def next(): Any
|
| @scala.annotation.tailrec
| final def last(): Any = {
| val n = next()
| if (n.isInstanceOf[Cons[_]])
| n.asInstanceOf[Cons[_]].last()
| else
| n
| }
| }
<console>:14: error: could not optimize @tailrec annotated method last: it changes type of 'this' on a polymorphic recursive call
n.asInstanceOf[Cons[_]].last()
^
If we cheat and cast to Cons[A]
(because we can), it works:
scala> trait Cons[A] {
| def next(): Any
|
| @scala.annotation.tailrec
| final def last(): Any = {
| val n = next()
| if (n.isInstanceOf[Cons[_]])
| n.asInstanceOf[Cons[A]].last()
| else
| n
| }
| }
defined trait Cons
@sjrd :+1:
@sjrd I think it's a different problem.
In the example that I provided, the error position is notCons
. The error position suggests there is a type unification inserted at the end of the match
, which prevents tail-call optimization.
The position of the error is definitely off, but it is the problem I describe. You can also "fix" the problem with a .asInstanceOf[Cons[A]]
in your original example:
scala> :paste
// Entering paste mode (ctrl-D to finish)
trait Cons[A] {
def next(): Any
@scala.annotation.tailrec
final private def last(): Any = {
next() match {
case cons: Cons[_] =>
cons.asInstanceOf[Cons[A]].last()
case notCons =>
notCons
}
}
}
// Exiting paste mode, now interpreting.
defined trait Cons
scala/scala#6065 would allow a workaround:
trait Cons[A] {
def next(): Any
def last(): Any = {
@scala.annotation.tailrec
def go[T](c: Cons[T]): Any =
c.next() match {
case cons: Cons[_] =>
go(cons)
case notCons =>
notCons
}
go(this)
}
}