3

CSの基礎をブラッシュアップするために、いくつかの基本的な抽象データ型とアルゴリズムを作成し、その過程でScalaを学習しています。より抽象的なBinaryTreeの実装であるBinarySearchTreeデータ型で問題が発生しています。

abstract class BinaryTree[T](stored_value: T) { 
  var contents = stored_value
  var l: this.type = _
  var r: this.type = _
  ...
}

class BinarySearchTree[T <: Ordered[T]](stored_value: T) extends BinaryTree(stored_value) {  
  def insert(newval: T) {
    if (newval <= contents) {
      if (l == null) {
        throw new NotDefinedError("Still trying to work around type erasure.")
      } else {
        l.insert(newval)
      }
    } else {
      if (r == null) {
        throw new NotDefinedError("Still trying to work around type erasure.")
      } else {
        r.insert(newval)
      }
    }
  }

l = new this.type(newval)NotDefinedErrorsthis.typeをスローするブロックでは、のようないくつかのアプローチを試しましたBinarySearchTree[T]。そのタイプをどのように表現しようとするかに応じて、次のようになります。

class type required but BinarySearchTree.this.type found

また：

type mismatch;  found   : trees.BinarySearchTree[T]  required: BinarySearchTree.this.type

BinarySearchTreeの定義でlとrを異なるタイプでオーバーライドする必要がありますか？または、新しい値をアタッチするときに、別のタイプのコンストラクターを呼び出すだけですか？または他のオプション？

4

2 に答える 2

7

現在の方向性の代わりに不変のツリーデータ構造を探索するという@dhgの推奨に同意します。ただし、可変ツリーが本当に必要なものである場合は、以下をお読みください...

あなたの当面の問題はthis.type、の定義において、BinaryTree[T]それが何を意味すると思うかを意味しないということです。これは、実際には、囲んでいるインスタンスのシングルトンタイプです。住んでいたタイプと他にはthis何もありません。これを説明する例を次に示します。

scala> class Foo { def self : this.type = this /* OK */ }
defined class Foo

scala> class Bar { def self : this.type = new Bar /* Does not compile */ }
<console>:7: error: type mismatch;
 found   : Bar
 required: Bar.this.type
       class Bar { def self : this.type = new Bar /* Does not compile */ }
                                          ^

これは明らかに、実際に必要なタイプよりもはるかに具体的なタイプです。

問題を解決するための1つのオプションは、@ dhgの回答のように、とlのタイプを弱めることです。ただし、元々使用していたのは、ツリーノードを自己型化し、サブクラスのBinarySearchTree[T]に改良することだったと思います。これは、再帰型がバインドされたJavaの場合と同じように実行できます。または、次のような抽象型メンバーを使用して実行できます。rBinaryTree[T]this.type

abstract class BinaryTree[T] {
  type Self <: BinaryTree[T]
  var contents : T
  var l: Self = _
  var r: Self = _
}

class BinarySearchTree[T <: Ordered[T]](stored_value : T) extends BinaryTree[T] {
  type Self = BinarySearchTree[T]
    var contents = stored_value
    def insert(newval: T) {
      if (newval <= contents) {
        if (l == null) {
          new BinarySearchTree(newval)
        } else {
          l.insert(newval)
        }
      } else {
        if (r == null) {
          new BinarySearchTree(newval)
        } else {
          r.insert(newval)
        }
      }
  }
}
于 2012-05-06T09:16:31.577 に答える
6

私はそれを次のように定義します：

class BinaryTree[T](
  val item: T,
  val left: Option[BinaryTree[T]] = None,
  val right: Option[BinaryTree[T]] = None) {

  override def toString() = "Tree(%s,%s,%s)".format(item,left,right)
}

class BinarySearchTree[T: Ordering](
  override val item: T,
  override val left: Option[BinarySearchTree[T]] = None,
  override val right: Option[BinarySearchTree[T]] = None) extends BinaryTree[T](item, left, right) {

  def insert(newval: T): BinarySearchTree[T] = {
    val (newLeft, newRight) =
      if (implicitly[Ordering[T]].lteq(newval, item))
        (insertSubtree(newval, left), right)
      else
        (left, insertSubtree(newval, right))
    new BinarySearchTree(item, newLeft, newRight)
  }

  private def insertSubtree(newval: T, subtree: Option[BinarySearchTree[T]]) =
    Option(subtree
      .map(_.insert(newval))
      .getOrElse(new BinarySearchTree(newval, None, None)))
}

私がScalaに似たものに変更した基本的なものがいくつかあります。

  • すべてのvalフィールドを使用して、構造を不変にします。insert新しい変更されたツリーを返します。メモリの浪費を避けるために、できるだけ古い（不変の）ツリーを保持してください。
  • 代わりに使用nullして使用することは避けてください。Optionしたがって、leftおよびrightサブツリーはOption[Binary(Search)Tree[T]]であり、それらが存在する場合と存在しない場合があることを明示的に示します。
  • mapですので、サブツリーで利用してくださいOption。このコードはinsertSubtree基本的に「サブツリーが存在する場合はそのサブツリーに挿入します。そうでない場合は新しいツリーを取得します」と述べています。

仕組みは次のとおりです。

scala> var t = new BinarySearchTree(5, None, None)
t: BinarySearchTree[Int] = Tree(5,None,None)

scala> t = t.insert(3)
t: BinarySearchTree[Int] = Tree(5,Some(Tree(3,None,None)),None)

scala> t = t.insert(4)
t: BinarySearchTree[Int] = Tree(5,Some(Tree(3,None,Some(Tree(4,None,None)))),None)

scala> t = t.insert(7)
t: BinarySearchTree[Int] = Tree(5,Some(Tree(3,None,Some(Tree(4,None,None)))),Some(Tree(7,None,None)))
于 2012-05-06T01:52:57.707 に答える