通用優先級隊列中的同向和反向類型

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可用...）