Co- and contravariant types in the general priority queue

Question

I am trying to implement a common data type in Scala, parameterized by the type Tthat should be Ordered[T]. In particular, this is a constant version of the priority queues "Slitor" and "Tarjan" skew heap . After adding many descriptions of parameters of a complex type based on the explanation here and in Odersky-Spoon-Venners, I came to one compiler error before I can check / debug the actual functionality.

The following is a simplified code of my code.

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
}

This results in the following error:

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 , <% 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
}

Foo , . , :

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

After that you can create Foo[Bar].

(Sorry for the simplest example, my computer crashed and I don't have an IDE ...)