Scala: A extends Ordered[A]

Question

I've just started learning Scala and I decided, for practice, to create a Pair[A, B] class that when sorted will first be sorted by As and then by Bs. My first attempt was this:

case class Pair[A <: Ordered[A], B <: Ordered[B]](val left: A, val right: B) extends Ordered[Pair[A, B]]
{
  override def compare(that: Pair[A, B]) = {
      val leftCompare = this.left.compare(that.left)
      if (leftCompare == 0)
        this.right.compare(that.right)
      else
        leftCompare
    }
}

object Main extends App
{
  List(Pair(1, "a"), Pair(5, "b"), Pair(5, "a"), Pair(1, "b")).sorted
}

This is the way I want it to be done, really. I want to extend Ordered and have it work from that, so I can just do things like List(whatever).sortWith(_ < _) or List(whatever).sorted, like I've written in Main. I get the following errors:

pair.scala:14: error: inferred type arguments [Int,String] do not conform to method apply's type parameter bounds [A <: Ordered[A],B <: Ordered[B]]
  List(Pair(1, "a"), Pair(5, "b"), Pair(5, "a"), Pair(1, "b")).sorted

and this for every pair in the list:

pair.scala:14: error: type mismatch;
 found   : Int(1)
 required: A
  List(Pair(1, "a"), Pair(5, "b"), Pair(5, "a"), Pair(1, "b")).sorted

and this as well, which I have no understanding of:

pair.scala:14: error: diverging implicit expansion for type scala.math.Ordering[Pair[_ >: A with A with A with A <: scala.math.Ordered[_ >: A with A with A with A <: scala.math.Ordered[_ >: A with A with A with A]], _ >: B with B with B with B <: scala.math.Ordered[_ >: B with B with B with B <: scala.math.Ordered[_ >: B with B with B with B]]]]
starting with method $conforms in object Predef
  List(Pair(1, "a"), Pair(5, "b"), Pair(5, "a"), Pair(1, "b")).sorted

I managed to get it to sort, but only by writing sorting functions that were aware of the types they were sorting, rather than just being aware they were sorting types that are sortable. Here's what these "aware of the types" versions are, as I've mentioned them:

case class Pair[A, B](val left: A, val right: B)
{}

object Main extends App
{
  val pairs = Array(Pair(1, "a"), Pair(5, "b"), Pair(5, "a"), Pair(1, "b"))
  Sorting.quickSort(pairs)(Ordering[(Int, String)].on(x => (x.left, x.right)))
  println(pairs.toList)
}

and

case class Pair[A, B](val left: A, val right: B)
{}

object Main extends App
{
  val intStringSort = (x: Pair[Int, String], y: Pair[Int, String]) => {
    val intCompare = x.left - y.left
    if (intCompare == 0)
      x.right.compare(y.right) < 0
    else
      intCompare < 0
  }
  println(List(Pair(1, "a"), Pair(5, "b"), Pair(5, "a"), Pair(1, "b")).sortWith(intStringSort))
}

Thanks in advance.

Answer 1

Use <% instead of <:

case class Pair[A <% Ordered[A], B <% Ordered[B]]

because neither Int nor String are Ordered.

UPDATE:

But there are implicit conversions from Int to RichInt which is Ordered[Int] and from String to StringOps which is Ordered[String].

<% means that object can be implicitly converted to defined type. For example, A <% Ordered[A] for Int means that there is an implicit conversion from Int to Ordered[Int] which is:

implicit def intWrapper(x: Int)         = new runtime.RichInt(x)

in scala.Predef which is imported automatically. RichInt is Ordered[Int]. Similar steps are performed for String.