Scala types and inheritance

Question

I've got an interface,

trait Heap[E, H <: Heap[E, H]] {
  implicit def ord: Ordering[E]

  def empty: H

  def isEmpty: Boolean

  def insert(x: E): H

  def merge(b: H): H

  def findMin: E

  def deleteMin: H

  def toList: List[E] =
    if (isEmpty) Nil else findMin :: deleteMin.toList
}

It's generic, as we need H to define "a Heap of the same type," as def merge(b: H): H is normally defined in terms of merging heaps of the same internal structure.

That works reasonably well for the "normal" heaps, i.e. heaps that manage their internal structures themselves:

class LazyPairingHeap[E](val h: Repr[E] = Empty)
                        (implicit val ord: Ordering[E])
  extends Heap[E, LazyPairingHeap[E]] {

  import okasaki.heaps.LazyPairingHeap._

  override def empty = new LazyPairingHeap[E](Empty)

  override def isEmpty: Boolean = h == Empty

  // etc.

and even for some of the heaps build on top of other heaps:

class SizedHeap[E, H <: Heap[E, H]](val s: Int, val h: H)
    extends Heap[E, SizedHeap[E, H]] {

  override implicit def ord: Ordering[E] = h.ord

  override def empty = new SizedHeap[E, H](0, h.empty)

  override def isEmpty = s == 0

  override def insert(e: E) = new SizedHeap[E, H](s + 1, h.insert(e))

  override def merge(o: SizedHeap[E, H]) = new SizedHeap[E, H](s + o.s, h.merge(o.h))

  override def findMin: E = h.findMin

  override def deleteMin = new SizedHeap[E, H](s - 1, h.deleteMin)
}

The problem appears when instead of merely wrapping the original heap we need to weave it into our representation:

object BootstrappedHeap {

  sealed trait BSHeap[+A, +H[_]]

  object Empty extends BSHeap[Nothing, Nothing] {
    override def toString = "Empty"
  }

  case class H[A, BH[_]](x: A, bsh: BH[BSHeap[A, BH]]) extends BSHeap[A, BH] {
    override def toString = s"H($x, $bsh)"
  }

}

abstract class BootstrappedHeap[E,
                                BaseHeap[X] <: Heap[X, BaseHeap[X]],
                                This <: BootstrappedHeap[E, BaseHeap, This]]
          (val h: BSHeap[E, BaseHeap] = Empty)
          (implicit ord: Ordering[E])
  extends Heap[E, This] {

  implicit val hord: Ordering[BSHeap[E, BaseHeap]] =
    Ordering.by {
      case Empty => None
      case H(x, _) => Some(x)
    }

  def baseHeap: BaseHeap[BSHeap[E, BaseHeap]]

  def create(h: BSHeap[E, BaseHeap]): This

  override def empty = create(Empty)

  override def isEmpty: Boolean = h == Empty

  override def insert(x: E) = create(merge(H(x, baseHeap.empty), h))

  override def merge(o: This) = create(merge(h, o.h))

  private def merge(a: BSHeap[E, BaseHeap], b: BSHeap[E, BaseHeap]): BSHeap[E, BaseHeap] = (a, b) match {
    case (Empty, _) => b
    case (_, Empty) => a
    case (h1@H(x, p1), h2@H(y, p2)) =>
      if (ord.lteq(x, y)) H(x, p1.insert(h2))
      else H(y, p2.insert(h1))
  }

  // etc

Now the question is, is there a better way than this lovely type annotation?

[E,
 BaseHeap[X] <: Heap[X, BaseHeap[X]],
 This <: BootstrappedHeap[E, BaseHeap, This]]

X seems to be unnecessary though I found no way to get rid of it;
a reference to This seems to be a bit over the edge;
finally, BaseHeap has really nothing to do in the public interface: I want it to be an implementation detail, can I hide it?

Scala types and inheritance

0 Answers