1

考虑这个简单的二叉树类型：

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类型中，但不会出现在具体实现中，例如指定ScapegoatTree位置Repr。basic 也有一个具体的实现BinaryTree，但我试图保持最小化，这样您就不必费力地处理太多不必要的代码。

4

1 回答 1

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”问题。

于 2012-07-13T02:04:08.140 回答