@tailrec錯誤「遞歸調用目標超類型」

Question

應用@tailrec我從scala編譯器收到錯誤：「無法優化@tailrec註釋方法get：它包含一個遞歸調用，目標是一個超類case _ => tail.get第（n-1）」。有人能解釋爲什麼嗎？

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

試着想象這裏發生了什麼，以及你要求編譯器做什麼。粗略地說，尾調用優化將方法調用轉換爲循環，將方法的參數轉化爲在循環的每次迭代中重新分配的變量。

這裏有兩個這樣的「循環變量」：n和調用get方法的列表單元格本身，實際上它是方法體中的this。 n的下一個值是罰款：它是n - 1還有一個Int。列表單元格的下一個值爲tail，但存在一個問題：this的類型爲Cons[T]，但tail僅具有類型List[T]。

因此，編譯器無法將其變成循環，因爲不能保證tail是Cons[T]--而且足夠肯定的是，在列表末尾，它是一個Nil。

一種方式來「修復」這將是：

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

（工程如果兩個Cons和Nil是case類 - 但你可能會希望Nil一個case object和List[T]協在T）

Answer 2

在Cons.get你可以撥打tail.get作爲你的尾巴。但是tail的類型爲List[T]，而不是Cons[T]。所以這個調用不一定會被Cons.get處理，Scala不能應用尾遞歸優化;優化會將方法調用轉變爲本地跳回到Cons.get的開始，但這不一定是通話的去向。

Answer 3

Ben和Jean-Phillipe Pellet已經解釋了爲什麼編譯器會抱怨。至於如何解決這個問題，有一個簡單的解決方案：移動的get實施右轉入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") 
}