为什么这段代码不编译？这真的不安全吗？

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

在Scala IDE中使用Scala 2.9，add方法无法编译，因为copy使用Repr，而left.add(elem)和right.add(elem)返回Repr#Repr。据我所知，Repr#Repr必须始终是Repr的一个亚型，因此它应该是安全的。我有没有考虑过一些情况，或者这是一个幸运的罕见例子，类型系统阻止你做一些应该工作的事情？

此外，有没有任何方法可以更改我的类型定义，使其合法，或者向编译器断言Repr#Repr必须是Repr的子类型（我的意思是，除了强制转换）。我仍然习惯Scala，我不确定我是否已经完全理解了类型系统。我确实通过编写一个执行强制转换的隐式方法来编译它，但这感觉更像是一种变通方法，而不是解决方案。

提前感谢您的帮助。

编辑：我应该补充一点，在我的实际实现中，我有进一步限制Repr类型的子类，如果这有区别的话。

编辑2：根据要求添加更多代码。这个问题也出现在BinarySearchTree类型中，但在指定Repr的ScapegoatTree等具体实现中没有出现。还有一个基本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 )
}

根据这个问题，您正在计算一个"MyType"问题。