爲什麼不編譯這個代碼？這真的是不安全的？

Question

考慮一個簡單的二叉樹類型：

abstract class BinaryTree[T] { 
    type Repr <: BinaryTree[T] 

    def left: Repr 
    def value: T 
    def right: Repr 

    def height: Int 

def add(elem: T): Repr = 
    if (left.height <= right.height) copy(left.add(elem), right) 
    else copy(left, right.add(elem)) 

def copy(left: Repr, right: Repr) : Repr 
} 

abstract class BinarySearchTree[T] extends BinaryTree[T] { 
    type Repr <: BinarySearchTree[T] 

    def ordering: Ordering[T] 

    override def add(elem: T) = 
    if (ordering.equiv(elem, value)) this.asInstanceOf[Repr] 
    else if (ordering.lt(elem, value)) copy(left.add(elem), right) 
    else copy(left, right.add(elem)) 
} 


class ScapegoatTree[T](val value: T, val left: ScapegoatTree[T], val right: ScapegoatTree[T])(implicit val ordering: Ordering[T]) 
    extends BinarySearchTree[T] { 

    type Repr = ScapegoatTree[T] 

    def add = this /* snip */ 

    def copy(left: ScapegoatTree[T], right: ScapegoatTree[T]) = new ScapegoatTree(value, left, right) 
} 

class BalancedBinaryTree[T](val value: T, val left: BalancedBinaryTree[T], val right: BalancedBinaryTree[T])(implicit val ordering: Ordering[T]) 
    extends BinarySearchTree[T] { 

    type Repr = BalancedBinaryTree[T] 

    def add = this /* snip */ 

    def copy(left: BalancedBinaryTree[T], right: BalancedBinaryTree[T]) = new BalancedBinaryTree(value, left, right) 
} 

在斯卡拉-IDE使用斯卡拉2.9，add方法編譯失敗，因爲副本需要Repr而left.add(elem)和right.add(elem)返回Repr#Repr。據我所知，Repr#Repr必須始終是Repr的子類型，因此它應該是安全的。我有沒有考慮過某種情況，還是幸運的是這種類型系統妨礙你做某些應該工作的罕見情況？另外，有沒有什麼辦法可以改變我的類型定義，所以這將是合法的，或者向編譯器斷言Repr#Repr必須是Repr的子類型（我的意思是除了cast之外）。我仍然習慣了Scala，我不確定我是否完全理解了類型系統。我確實通過編寫一個隱式方法來進行編譯，但這種解決方案更像是一種解決方法。

在此先感謝您的幫助。

編輯：我應該補充一點，在我的這個實際實現中，我有一些子類，這些子類會進一步限制Repr的類型，如果這樣做有所幫助的話。

編輯2：根據要求添加更多代碼。此問題也出現在BinarySearchTree類型中，但不在具體實現中，例如ScapegoatTree，其中指定了Repr。還有一個基本的BinaryTree的具體實現，但我試圖保持它最小，所以你不必趟過太多不必要的代碼。

Answer 1

剛剛嘗試過使用類型參數而不是抽象類型重寫，希望它適合您的需要。

trait BinaryTree[T, Repr <: BinaryTree[T, Repr]] { 
    def left: Repr 
    def value: T 
    def right: Repr 

    def height: Int 
    def add(elem: T): Repr = 
    if (left.height <= right.height) copy(left.add(elem), right) 
    else copy(left, right.add(elem)) 

    def copy(l: Repr, r: Repr) : Repr 
} 

trait BinarySearchTree[T, U<:BinarySearchTree[T,U]] extends BinaryTree[T, U] { self:U => 
    def ordering: Ordering[T] 

    override def add(elem: T) = 
    if (ordering.equiv(elem, value)) self 
    else if (ordering.lt(elem, value)) copy(left.add(elem), right) 
    else copy(left, right.add(elem)) 
} 

class ScapegoatTree[T](val value: T, val left: ScapegoatTree[T], val right: ScapegoatTree[T])(implicit val ordering: Ordering[T]) extends BinarySearchTree[T, ScapegoatTree[T]] { 
    override def height = 1 
    override def copy(left: ScapegoatTree[T], right: ScapegoatTree[T]) = new ScapegoatTree(value, left, right) 
} 

class BalancedBinaryTree[T](val value: T, val left: BalancedBinaryTree[T], val right: BalancedBinaryTree[T])(implicit val ordering: Ordering[T]) extends BinarySearchTree[T, BalancedBinaryTree[T]]{ 
    override def height = 1 
    override def copy(left: BalancedBinaryTree[T], right: BalancedBinaryTree[T]) = new BalancedBinaryTree(value, left, right) 
} 

根據this question，您正在引發'MyType'問題。