How scala orders tuples?

Question

I'm trying to understand how scala handles ordering and sorting of tuples

For example, if I got the list

val l = for {i <- 1 to 5} yield (-i,i*2)
Vector((-1,2), (-2,4), (-3,6), (-4,8), (-5,10))

scala knows how to sort it:

l.sorted
Vector((-5,10), (-4,8), (-3,6), (-2,4), (-1,2))

But tuple don't have a '<' method:

l.sortWith(_ < _)

error: value < is not a member of (Int, Int)
l.sortWith(_ < _)

How does scala know how to sort those tuples?

Answer 1

Because sorted have an implicit parameter ord:

def sorted[B >: A](implicit ord: math.Ordering[B]): List[A] Sorts this sequence according to an Ordering.

The sort is stable. That is, elements that are equal (as determined by lt) appear in the same order in the sorted sequence as in the original.

ord the ordering to be used to compare elements.

and there is an implicit conversion defined in scala.math.Ordering:

implicit def Tuple2[T1, T2](implicit ord1: Ordering[T1], 
                                     ord2: Ordering[T2]): Ordering[(T1, T2)]

So l.sorted will be transformed to l.sorted(scala.math.Ordering.Tuple2[Int, Int]()).

Test it:

scala> def catchOrd[A](xs: A)(implicit ord: math.Ordering[A]) = ord
catchOrd: [A](xs: A)(implicit ord: scala.math.Ordering[A])scala.math.Ordering[A]

scala> catchOrd((1,2))
res1: scala.math.Ordering[(Int, Int)] = scala.math.Ordering$$anon$11@11bbdc80

And of course, you can defined your own Ordering:

scala> implicit object IntTupleOrd extends math.Ordering[(Int, Int)] {
     |   def compare(x: (Int, Int), y: (Int, Int)): Int = {
     |     println(s"Hi, I am here with x: $x, y: $y")
     |     val a = x._1*x._2
     |     val b = y._1*y._2
     |     if(a > b) 1 else if(a < b) -1 else 0
     |   }
     | }
defined object IntTupleOrd

scala> Seq((1, 10), (3, 4),  (2, 3)).sorted
Hi, I am here with x: (1,10), y: (3,4)
Hi, I am here with x: (3,4), y: (2,3)
Hi, I am here with x: (1,10), y: (2,3)
res2: Seq[(Int, Int)] = List((2,3), (1,10), (3,4))

EDIT There is a short way to make Tuple[Int, Int] support all the following methods: <, <=, >, >=.

scala> implicit def mkOps[A](x: A)(implicit ord: math.Ordering[A]): ord.Ops =
     |   ord.mkOrderingOps(x)
mkOps: [A](x: A)(implicit ord: scala.math.Ordering[A])ord.Ops

scala> (1, 2) < (3, 4)
res0: Boolean = true

scala> (1, 2) <= (3, 4)
res1: Boolean = true

scala> (1, 2, 3) <= (1, 2, 4)
res2: Boolean = true

scala> (3, 3, 3, 3) >= (3, 3, 3, 4)
res3: Boolean = false