通用堆的 Scala 实现

Question

我正在尝试实现一个非常基本的泛型堆实现，虽然我喜欢类型检查器，但这是我觉得它每一步都在与我作斗争的场合之一。

我能写的最简单的表达式是:

trait Heap[A] {
  def isEmpty: Boolean
  def merge(as: Heap[A]): Heap[A]
  def insert(a: A): Heap[A]
  def findMin: A
  def deleteMin(): Heap[A]
}

这很好，但具体实现会在 merge 时“松散”它们的类型。 , insert或 deleteMin被称为。也就是说，如果 set是 CustomHeap 类型, 调用 set.deleteMin是 Heap 类型.

经过一番努力，我想出了以下定义来解决这个问题:

trait Heap[A, Repr <: Heap[A, Repr]] {
  def isEmpty: Boolean
  def merge(as: Repr): Repr
  def insert(a: A): Repr
  def findMin: A
  def deleteMin(): Repr
}

这开始变得复杂，但按预期工作:它是通用的 Heap ，并且在调用 merge 时类型不会丢失， 例如。

当一个人试图不将自己的代码绑定(bind)到 Heap 的特定实现时，这个定义有点麻烦。 , 但是:变量不能是 Heap[A] 类型但是更复杂的东西我很快就放弃了尝试写。

为了解决这个限制，我尝试使用 XxxLike在集合 API 中随处可见的模式，但这是我卡住的地方。

这就是我到目前为止所拥有的:

trait Heap[A] extends HeapLike[A, Heap[A]]

trait HeapLike[A, +Repr <: HeapLike[A, Repr] with Heap[A]] {
  def isEmpty: Boolean
  def merge(bs: Repr): Repr
  def insert(a: A): Repr
  def findMin: A
  def deleteMin(): Repr
}

这是相当复杂的，并且引入了一个新的特征只是为了打字，但我可以忍受 - 如果它有效。

有了这个实现， HeapLike在 Repr 上是协变的, 但是 Repr是 merge 的参数- 逆变位置的协变类型。我无法解决这个问题。

我也尝试制作 HeapLike Repr 上的非变量，在我尝试将特征实际混合之前，它工作正常:

sealed trait LeftistHeap[A] extends Heap[A] with HeapLike[A, LeftistHeap[A]] {
  def rank: Int
}

这会产生以下错误消息:

error: illegal inheritance;
self-type this.LeftistHeap[A] does not conform to this.HeapLike[A,this.LeftistHeap[A]]'s selftype this.HeapLike[A,this.LeftistHeap[A]]
sealed trait LeftistHeap[A] extends Heap[A] with HeapLike[A, LeftistHeap[A]] {

我敢肯定有一种简单的方法可以让这一切正常工作——它比集合 API 更基本一些，它设法完成所有这些并且对集合中包含的元素保持协变，但我觉得我已经撞到一堵砖墙。任何建议，解释，指针......？

Answer 1

实际上，Scala 中的方差非常棒，可以让您更简单地解决问题。

让我们把你原来的Heap特征:

trait Heap[A] {
  def isEmpty: Boolean
  def merge(as: Heap[A]): Heap[A]
  def insert(a: A): Heap[A]
  def findMin: A
  def deleteMin(): Heap[A]
}

...为了让派生集合在应用转换后保持其“种类”，您可以执行以下操作(我在这里演示概念，所以我使用 ??? stub 方法。此代码将编译但您显然必须实现它们以使您的堆在运行时工作):

class MyHeap[A] extends Heap[A] {
  override def isEmpty: Boolean = ???
  override def insert(a: A): MyHeap[A] = ???
  override def deleteMin(): MyHeap[A] = ???
  override def merge(as: Heap[A]): MyHeap[A] = ???
  override def findMin: A = ???
}

...然后你可以做这样的事情:

val myHeap1 = new MyHeap[Int]
val myHeap2 = new MyHeap[Int]

val stillMyHeap1: MyHeap[Int] = myHeap1 insert 1
val stillMyHeap2: MyHeap[Int] = myHeap1 merge myHeap2

请注意 insert , deleteMin和 merge return types are covariant ( MyHeap)。

另请注意 merge接受相同类型的参数( Heap )，但您也可以将其实现为 take contravariant argument type如果您愿意(即 Heap 的假设基数)。

更新

顺便说一句，制作 Heap[A] (或 MyHeap[A] )保留其参数类型的方差 A ，就像标准的 Scala 集合一样(例如:对于 AnyVal 是 Int 的基础，有 Heap[AnyVal] 是 Heap[Int] 的基础)你必须改变你的 Heap像这样的特质:

trait Heap[+A] {
  def isEmpty: Boolean
  def merge[B >: A](xs: Heap[B]): Heap[B]
  def insert[B >: A](x: B): Heap[B]
  def findMin: A
  def deleteMin(): Heap[A]
}

...和 MyHeap像这样:

class MyHeap[+A] extends Heap[A] {
  override def isEmpty: Boolean = ???
  override def insert[B >: A](x: B): MyHeap[B] = ???
  override def deleteMin(): MyHeap[A] = ???
  override def merge[B >: A](xs: Heap[B]): MyHeap[B] = ???
  override def findMin: A = ???
}

...然后您可以按如下方式使用它:

val myHeap1 = new MyHeap[Int]
val myHeap2 = new MyHeap[Int]

val stillMyHeap1: MyHeap[Int] = myHeap1 insert 1
val stillMyHeap2: MyHeap[Int] = myHeap1 merge myHeap2

val myHeap3: MyHeap[AnyVal] = myHeap1
val myHeap4: MyHeap[AnyVal] = myHeap1 insert 'a'

val heap1: Heap[Int] = myHeap1
val heap2: Heap[AnyVal] = myHeap1

注意 MyHeap[Int]符合所有这些:

MyHeap[AnyVal] ( myHeap3 )

Heap[Int] ( heap1 )

Heap[AnyVal] ( heap2 )

还要注意 insert学习 Char进入 MyHeap[Int]生产 MyHeap[AnyVal] ( myHeap4)。由于此操作的结果不能是 MyHeap[Int]也不是 MyHeap[Char]它回退到两个的共同祖先，即 MyHeap[AnyVal]