@tailrec error "recursive call targetting a supertype"
scala
Solution
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`.)
Problem
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)) } ```