@tailrec error "recursive call targetting a supertype"

Question

Applying @tailrec I'm getting error from scala compiler: "could not optimize @tailrec annotated method get: it contains a recursive call targetting a supertype case _ => tail.get(n-1)". Could someone explain why is that?

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's happening here and what you're asking the compiler to do. Tail call optimization, roughly, turns the method call into a loop, taking the arguments of the method and turning them into variables that are reassigned at each iteration of the loop.

Here, there are two such “loop variables”: n and the list cell itself on which the get method is called, which is actually this in the method body. The next value for n is fine: it's n - 1 and also an Int. The next value for the list cell, which is tail, is a problem, however: this has type Cons[T], but tail only has type List[T].

Thus, there is no way the compiler can turn it into a loop, as there is no guarantee that tail is a Cons[T] — and sure enough, at the end of the list, it is a Nil.

One way to “fix” it would be:

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

(Works if both Cons and Nil are case classes — but you'll probably want to make Nil a case object and List[T] covariant in T.)