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 を使用すると、コピーに時間がReprかかり、. 私が知る限り、は常に のサブタイプでなければならないため、安全なはずです。いくつかのケースを考慮し損ねたのでしょうか、それともこれは、型システムが機能するはずのことを妨げてしまう幸運にもまれなケースの 1 つなのでしょうか?left.add(elem)right.add(elem)Repr#ReprRepr#ReprRepr

また、これが合法になるように型定義を変更する方法、または(キャストを除いて)Repr#Reprのサブタイプである必要があるコンパイラにアサートする方法はありますか? Repr私はまだ Scala に慣れていないので、型システムを完全に理解しているとは言えません。キャストを行う暗黙的なメソッドを作成してコンパイルすることはできましたが、それは解決策というよりも回避策のように感じます。

よろしくお願いします。

編集：これの実際の実装では、Reprのタイプをさらに制限するサブクラスがあることを追加する必要があります。

編集 2: 要求に応じてコードを追加しました。この問題は型にも現れますが、whereが指定さBinarySearchTreeれているなどの具体的な実装には現れません。基本的な の具体的な実装もありますが、不要なコードを使いすぎる必要がないように最小限に抑えようとしています。ScapegoatTreeReprBinaryTree

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 に答える