scala - 通用优先级队列中的协变和逆变类型

Question

我正在尝试在 Scala 中实现一个通用数据类型，该类型在类型 T 上进行参数化，该类型应该是 Ordered[T]。具体来说，它是 Sleator & Tarjan 的 skew heap 的永久版本。优先队列。在根据解释添加大量复杂的类型参数声明后here在 Odersky-Spoon-Venners 中，在我可以测试/调试实际功能之前，我遇到了一个编译器错误。

下面是我的代码的简化版本。

abstract class SkewHeap[+T] {
  // merge two heaps
  def +[U >: T <% Ordered[U]](x : SkewHeap[U]) : SkewHeap[U]
  // remove least element, return new heap
  def delMin[U >: T <% Ordered[U]] : SkewHeap[U]
  def isEmpty : Boolean
  def min : T
  def left  : SkewHeap[T]
  def right : SkewHeap[T]
}

case object Leaf extends SkewHeap[Nothing] {
  def +[U <% Ordered[U]](that : SkewHeap[U]) = that
  def isEmpty = true
}

case class Node[+T](left : SkewHeap[T],
                    min : T,
                    right : SkewHeap[T]) extends SkewHeap[T] {
  def +[U >: T <% Ordered[U]](that : SkewHeap[U]) : SkewHeap[U] =
    that match {
      case Leaf        => this
      case Node(l,y,r) => if (this.min < that.min)
                            Node(this.right + that, this.min, this.left)
                          else
                            Node(this + that.right, that.min, that.left)
    }

  def delMin[U >: T <% Ordered[U]] : SkewHeap[U] = left + right
  def isEmpty = false
}

这会产生以下错误:

skew.scala:28: error: no implicit argument matching parameter type (T) => Ordered[T] was found.
   def delMin[U >: T <% Ordered[U]] : SkewHeap[U] = left + right

我尝试了几种delMin 声明的变体，但都无济于事。我想我理解这个问题(方法 + 想要一个顺序保证)，但是我应该把它放在哪里？有没有办法将 delMin 声明为返回 SkewHeap[T] 而不是 SkewHeap[U]？

Answer 1

abstract class SkewHeap[+T <% Ordered[T]] {
  // merge two heaps
  def +[U >: T <% Ordered[U]](x : SkewHeap[U]) : SkewHeap[U]
  // remove least element, return new heap
  def delMin : SkewHeap[T]
  def isEmpty : Boolean
  def min : T
  def left  : SkewHeap[T]
  def right : SkewHeap[T]
}

case object Leaf extends SkewHeap[Nothing] {
  def +[U <% Ordered[U]](that : SkewHeap[U]) = that
  def isEmpty = true
  def min = throw new RuntimeException
  def left = throw new RuntimeException
  def right = throw new RuntimeException
  def delMin = throw new RuntimeException
}

Scala 不确定如何比较 this.min与 that.min ，因为它想转换 this.min到Ordered[T]和 that.min到Ordered[U] .最简单的答案是添加类型转换以强制 this.min到Ordered[U] .

case class Node[+T <% Ordered[T]](left : SkewHeap[T],
                    min : T,
                    right : SkewHeap[T]) extends SkewHeap[T] {
  def +[U >: T <% Ordered[U]](that : SkewHeap[U]) : SkewHeap[U] =
    that match {
      case Leaf        => this
      case Node(l,y,r) => if ((this.min:Ordered[U]) < that.min)
                            Node(this.right + that, this.min, this.left)
                          else
                            Node(this + that.right, that.min, that.left)
    }

  def delMin : SkewHeap[T] = left + right
  def isEmpty = false
}

但是所有这些隐式都有一个大问题，这个问题是您可能会得到一个不同的 Ordered在使用 View 绑定(bind)的每个上下文中的实现 <% Ordered[Something] , 所以你真的应该寻找其他方法来确保你的顺序是一致的。