CODEWITHSUNDEEP
scala
Konstantin Milyutin
Konstantin Milyutin

Reputation: 12356

@tailrec error "recursive call targetting a supertype"

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

Upvotes: 4

Views: 451

Answers (3)

Régis Jean-Gilles
Régis Jean-Gilles

Reputation: 32719

Ben and Jean-Phillipe Pellet have already explained why the compiler complains. As for how to fix it, there is a straightforward solution: move the implementation of get right into 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")
}

Upvotes: 2

Jean-Philippe Pellet
Jean-Philippe Pellet

Reputation: 59994

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

Upvotes: 6

Ben
Ben

Reputation: 71400

In Cons.get you call tail.get as your tail call. But tail is of type List[T], not Cons[T]. So that call won't necessarily be handled by Cons.get, and Scala can't apply the tail recursion optimisation; the optimisation would turn the method call into a local jump back to the start of Cons.get, but that's not necessarily where the call is going.

Upvotes: 2

Related Questions