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

发布时间：2020-12-16 10:08:14 所属栏目：安全来源：网络整理

导读：我正在创建一些基本的抽象数据类型和算法,以便了解我的CS基础知识,并在此过程中学习 Scala.我遇到了BinarySearchTree数据类型的问题,这是一个更抽象的BinaryTree的实现： abstract class BinaryTree[T](stored_value: T) { var contents = stored_value var

我正在创建一些基本的抽象数据类型和算法,以便了解我的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？或者在我为它们附加新值时调用不同类型的构造函数？还是其他一些选择？

解决方法

我同意@dhg的建议,即探索不可变树数据结构作为当前方向的替代方案.但是,如果一棵可变的树真的是你需要的,那么请继续阅读……

你当前的问题是BinaryTree [T]定义中的this.type并不代表你认为它意味着什么.它实际上是封闭实例的单例类型,即.这种类型居住的类型,没有别的.这是一个说明的例子,

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!