通用优先级队列中的同向和反向类型

Question

我正试图在Scala中实现一个类型为T（应该是Ordered[T]）参数化的通用数据类型。具体来说，它是Sleader的持久版本& 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是不知道如何与that.min比较this.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 
} 

但你必须与所有这些implicits的一个大问题，那问题是，你可能会得到不同的Ordered实现在每一个地方，你使用绑定<% Ordered[Something]视图上下文，所以你应该寻找一些其他确保您的订购是一致的。

Answer 2

与其使用<%语法糖，我建议您手动添加隐式参数。这是一个很多更容易控制，而且肯定更容易地看到发生了什么事情：

def delMin[U >: T](implicit ord: U => Ordered[U]): SkewHeap[U] = left + right 

在你的情况下，使用<%运营商的问题是，它结合T而非U。因此，它正在寻找类型T => Ordered[U]的功能。事实上，你所有的方法都是这样做的，我怀疑这不是你想要的行为。

此外，在成语小记：这是习惯使用++运营商连接两个集合，和+操作添加一个值到现有的集合（见Vector，ArrayBuffer，并在几乎任何集合标准库）。

Answer 3

除了其他建议之外，您可能会考虑将Ordered切换为隐式参数Ordering [T]，该控件更容易控制，并为您提供更大的灵活性。

[编辑] 一个很简单的例子：

class Foo[T](val t:T)(implicit val ord: Ordering[T]) { 
    def min(that:Foo[T]) = if (ord.compare(this.t, that.t) < 0) this else that 
} 

这一点，你可以使用美孚为有一个排序的所有类型之后。当然你可以自己做一个：

implicit object barOrdering extends Ordering[Bar] {...} 

在此之后，你可以创建一个Foo[Bar]。

（对不起，我非常简单的例子，我的电脑坏了，我没有IDE可用...）