Immutable queues with covariant priorities with higher types

Question

Immutable queues with covariant priorities with higher types

I would like to define various implementations of immutable covariant priority queues. First of all, I would like all implementations to provide the following interface:

trait PQLike[T, This[_]] {
  def isEmpty : Boolean
  def enqueue[E >: T](x : E)(implicit ord : Ordering[E]) : This[E]
  def dequeue[T] : This[T]
  def first : T
}

so it Thismeans the constructor of the implementation type, and T- the type of elements stored in the queue. For example, if it LinearPriorityQueue[T]is an implementation of a priority queue, then I want the method enqueuefor to LinearPriorityQueuereturn LinearPriorityQueue.

I would also like to define a trait PriorityQueue[T](or abstract class) so that it is also possible to type all implementations of priority queues (in addition to their specific type) as PriorityQueues.

I tried something like this:

trait PriorityQueue[+T] extends PQLike[T, _ <: PQLike[_,_]]

trait LinearPriorityQueue[+T] extends PriorityQueue[T] with PQLike[T,LinearPriorityQueue]    

object EPQ extends LinearPriorityQueue[Nothing] {
  def isEmpty = true
  def first = throw new PriorityQueueException("first on empty queue")
  def dequeue = throw new PriorityQueueException("dequeue on empty queue")
  def enqueue[T](x : T) = NPQ(x,this)
}

case class NPQ[+T](x : T, q : LinearPriorityQueue[T]) extends LinearPriorityQueue[T] {
  def isEmpty = false
  def first = x
  def dequeue = q
  def enqueue[E >: T](y : E) = NPQ(y,this) // not real implementation
}

, , .

: , . , , ( , ):

trait IsPriorityQueue[+T, +Repr[+X] <: IsPriorityQueue[X,Repr]] {
  def isEmpty : Boolean
  def first : T
  def enqueue[E >: T](x : E)(implicit ord : Ordering[E]) : Repr[E]
  def dequeue : Repr[T]
}

trait PriorityQueue[+T] extends IsPriorityQueue[T, PriorityQueue]

trait LinearPriorityQueue[+T] extends PriorityQueue[T] with IsPriorityQueue[T,LinearPriorityQueue]

object EmptyLPQ extends LinearPriorityQueue[Nothing] {
  def isEmpty = true
  def first = throw new PriorityQueueException("first on empty queue")
  def dequeue = throw new PriorityQueueException("dequeue on empty queue")
  def enqueue[E](x : E)(implicit ord : Ordering[E]) = NodeLPQ(x,this)
}

case class NodeLPQ[+T](hd : T, tl : LinearPriorityQueue[T]) extends LinearPriorityQueue[T] {
  def isEmpty = false
  def first = hd
  def dequeue = tl
  def enqueue[E >: T](x : E)(implicit ord : Ordering[E]) =
    if(ord.compare(x,hd)<0)
      NodeLPQ(x,this)
    else
      NodeLPQ(hd,tl.enqueue(x))
}