Co- and contravariant types in generic priority queue

Question

I'm trying to implement in Scala a generic data type parameterized on a type T, which should be Ordered[T]. Specifically, it's a persistent version of Sleator & Tarjan's skew heap priority queues. After adding lots of complicated type parameter declarations based on the explanation here and in Odersky-Spoon-Venners, I'm down to one compiler error before I can test/debug the actual functionality.

Below is a simplified version 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 gives 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

I've tried several variants of the declaration of delMin, but to no avail. I think I understand the problem (method + wants an ordering guarantee), but where should I put this? And is there a way to declare delMin as returning SkewHeap[T] instead of 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 isn't sure how to compare this.min with that.min, becuase it wants to convert this.min to an Ordered[T] and that.min to an Ordered[U]. The simplest answer is to add a type conversion to force this.min to an 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
}

But you have a big problem with all of these implicits, and that problem is that you could get a different Ordered implementation in every context where you use the view bound <% Ordered[Something], so you should really look for some other way of making sure your ordering is consistent.

Answer 2

Rather than using the <% syntactic sugar, I suggest that you manually add the implicit parameter. It's a lot more controlled, and certainly easier to see what's going on:

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

The problem with using the <% operator in your case is it binds to T rather than U. Thus, it was looking for a function of type T => Ordered[U]. In fact, all of your methods are doing this, and I suspect that's not the behavior you wanted.

Also, a minor note on idioms: it is customary to use the ++ operator for concatenating two collections, and the + operator for adding a single value to an existing collection (see Vector, ArrayBuffer, and pretty much any collection in the standard library).

Answer 3

Additional to the other suggestions, you may consider to switch from Ordered to an implicit parameter Ordering[T], which is much easier to control and gives you more flexibility.

[Edit] A very simple example:

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
}

After this you can use Foo for all types that have an ordering. Of course you can make one yourself:

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

After this, you could create a Foo[Bar].

(Sorry for the very basic example, my PC broke down and I have no IDE available...)