如何在Scala中调用树代数数据类型的叶子的构造函数？

Question

我正在创建一些基本的抽象数据类型和算法,以便了解我的CS基础知识,并在此过程中学习Scala.我遇到了BinarySearchTree数据类型的问题,这是一个更抽象的BinaryTree的实现:

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

在抛出NotDefinedErrors块,我已经试过像几个方法l = new this.type(newval),替代this.type的BinarySearchTree[T]和其他任何我能想到的.根据我尝试表达该类型的方式,我得到的结果如下:

class type required but BinarySearchTree.this.type found

要么:

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

我是否需要在BinarySearchTree的定义中使用不同的类型覆盖l和r？或者在我为它们附加新值时调用不同类型的构造函数？还是其他一些选择？

Answer 1

我同意@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 */ }
                                          ^

这显然是一个比你真正想要的更具体的类型.

要解决这个问题的一个办法是削弱类型l和r到BinaryTree[T],如@ DHG的答案.但是,我认为你最初使用的this.type是对树节点进行自我类型化,并在子类中精炼为BinarySearchTree [T].您可以像在Java中使用递归类型绑定那样执行此操作,或者您可以使用类似的抽象类型成员执行此操作,

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

Answer 2

我会这样定义:

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