@tailrec error "recursive call targeting supertype"

Question

Using @tailrec I get an error from the scala compiler: "the @tailrec annotated method could not be optimized: it contains a recursive call for the supertype _ => tail.get (n-1)". Can anyone explain why this is?

trait List[T] { def isEmpty: Boolean def head: T def tail: List[T] def get(n: Int): T } class Cons[T](val head: T, val tail: List[T]) extends List[T]{ def isEmpty = false @tailrec final def get(n: Int) = n match { case 0 => head case _ => tail.get(n-1) } } class Nil[T] extends List[T]{ def isEmpty = true def head = throw new NoSuchElementException("Nil.head") def tail = throw new NoSuchElementException("Nil.tail") final def get(n: Int): T = throw new IndexOutOfBoundsException } object Main extends App{ println(new Cons(4, new Cons(7, new Cons(13, new Nil))).get(3)) } 

Answer 1

Try to imagine what is going on here and what you ask the compiler. Approximate call optimization, approximately, turns a method call into a loop, taking method arguments and turning them into variables that are reassigned at each iteration of the loop.

There are two such "loop variables" here: n and the list box itself on which the get method is called, which is actually this in the body of the method. The following value for n excellent: it is n - 1 , as well as Int . However, the following value for the tail list cell is a problem: this is of type Cons[T] , but tail is of type List[T] .

Thus, the compiler cannot turn it into a loop, since there is no guarantee that tail is Cons[T] - and, of course, at the end of the list it is Nil .

One way to "fix":

 case class Cons[T](val head: T, val tail: List[T]) extends List[T] { def isEmpty = false @tailrec final def get(n: Int) = n match { case 0 => head case _ => tail match { case c @ Cons(_, _) => c.get(n - 1) case nil @ Nil() => nil.get(n - 1) } } } 

(It works if both Cons and Nil are case classes, but you probably want to make Nil a case object and List[T] covariant in T )

Answer 2

In Cons.get you call tail.get as your tail call. But tail is of type List[T] , not Cons[T] . Thus, the call is not necessarily handled by Cons.get , and Scala cannot use tail recursion optimization; optimization will turn the method call into a local leap back to the beginning of Cons.get , but this is not necessary where the call goes.

Answer 3

Ben and Jean-Phillipe Pelle have already explained why the compiler complains. As for how to fix this, there is a direct solution: move the get implementation directly to List :

 trait List[T] { def isEmpty: Boolean def head: T def tail: List[T] @tailrec final def get(n: Int): T = { n match { case 0 => head case _ => tail.get(n-1) } } } class Cons[T](val head: T, val tail: List[T]) extends List[T]{ def isEmpty = false } class Nil[T] extends List[T]{ def isEmpty = true def head = throw new NoSuchElementException("Nil.head") def tail = throw new NoSuchElementException("Nil.tail") }