Pairing heap implementation

PairingHeap.scala

package ph

import scalaz._, Scalaz._

import scala.annotation.tailrec

sealed abstract class PairingHeap[A : Order] {

  def merge(that: PairingHeap[A]): PairingHeap[A] = this match {
    case Empty() => 
      that

    case Heap(thisA, thisHeaps) => that match {
      case Empty() =>
        this

      case Heap(thatA, thatHeaps) =>
        if (thisA < thatA) {
          Heap(thisA, that :: thisHeaps)
        } else {
          Heap(thatA, this :: thatHeaps)
        }
    }
  }

  def insert(a: A): PairingHeap[A] = merge(Heap(a, IList.empty))

  def uncons: Option[(A, PairingHeap[A])] = this match {
    case Empty() => None

    case Heap(a, heaps) =>
      Some((a, PairingHeap.mergePairs(heaps)))
  }

}
object PairingHeap {
  // TODO: tailrec?
  private def mergePairs[A : Order](list: IList[PairingHeap[A]]): PairingHeap[A] = {
    list match {
      case INil() =>
        empty

      case ICons(head, tail) =>
        tail match {
          case INil() =>
            head

          case ICons(x, xs) =>
            (head merge x) merge mergePairs(xs)
      }
    }
  }

  def empty[A](implicit ev: Order[A]): PairingHeap[A] = Empty()
}

case class Empty[A : Order]() extends PairingHeap[A]
case class Heap[A : Order](elem: A, subheaps: IList[PairingHeap[A]]) extends PairingHeap[A]