How scala orders tuples?

问题:

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?

回答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

回答2:

@Eastsun's answer nicely explains the first part of your question "how does Scala sort tuples".

Regarding the second part "why doesn't tuple have a < method": In Scala, comparators like < either translate to native JVM comparisons for basic types (when comparing Int or Double etc) or to member functions of someClass with the type <(that: someClass): Boolean. This case is actually just syntactic sugar: someObject < otherObject translates to someObject.<(otherObject). If you want to have this functionality for tuples, you can bring an implicit class into scope, and map the comparison member function to the comparators provided by the Ordering:

implicit class ProvideComparator[T](t1: T)(implicit ord: Ordering[T]) {
  def <(t2: T) = ord.lt(t1, t2)
  def >(t2: T) = ord.gt(t1, t2) // and so on
}

Now you can just write:

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