How to lexicographically compare scala tuples?

Question

Given two tuples of the same arity, how can I lexicographically compare them? It seems like this should be as simple as in the following snippet, but it isn't. Any simple example of how to do it?

var x = (1,2,3) < (1,2,4)

Were they lists, I could define a recursive function that would compare the lists' head until a difference or the end of a list was found, but I don't think I could do that for tuples.

Answer 1

It's not simple because while

var x = (1,2,3) < (1,2)

looks pretty simple,

var x = (1,false,3) < (1,2)

is not. How do you deal with non-ordered types? How do you deal with different types in the same tuple position?

Do you mandate all types to be the same? In that case, you do not have a tuple. The whole point of a tuple is that its arity is fixed (you statically know how big it is) and each element can be of a different type.

If I found myself with that problem -- and I'd try very hard not to -- I'd grab Shapeless, convert the tuples into something like HLists, and then try to compare on that.

EDIT

Ah, now it is much easier:

import scala.math.Ordering.Implicits._
var x = (1,2,3) < (1,2,4)

These extra implicits are not automatically available because they can result in diverging implicits under some circumstances.

Answer 2

Daniel's solution works if you want to use < but if you need a compare method you can do the following (for example).

implicitly[Ordering[Tuple2[Int, Int]]].compare((1,2), (2,3))

There are orderings defined for all tuples with comparable parts.

Answer 3

The easiest way is to define an implicit Ordering[T] on them, but then you have to pass this ordering to the sort function (or any other function that wants to compare them). It is also possible to pass it implicitly.

Another way would be, to extend the tuple class by the < operator via an implicit cast:

implicit def compareTuple[T](lhs: (T,T)) = new {
   def <(rhs: (T,T)) = lhs._1<rhs._1 || (lhs._1==rhs._1 && lhs._2<rhs._2)
}

edit: If you want to have the other comparison operators too, you could get them by inheriting from Ordered[T]:

implicit def compareTuple[T](lhs: (T,T)) = new Ordered[(T,T)] {
   def compare(rhs: (T,T)) = ...
}

edit2: If you also need to compare tuples of different sizes, you can use the productIterator function which is defined in all tuple classes (see documentation) and allows you to get an iterator over the tuple. This way you could write a function like you would do it with a list.

edit3: This would be something like:

implicit def compareTuple[T <: Product](lhs: T) = new Ordered[T] {
    def compare[U <: Product](rhs: U) = {
        def compare(lhs: Any, rhs: Any) = ...
        def iteratorCompare(lhs: Iterator[Any], rhs: Iterator[Any]):Int = 
            if(!lhs.hasNext)
                if(!rhs.hasNext)
                    0
                else
                    -1
            else if(!rhs.hasNext)
                1
            else
                compare(lhs.next,rhs.next)
        iteratorCompare(lhs.productIterator,rhs.productIterator)
    }
}

But with this approach you have to take care about the types. Because the function doesn't know the types of the tuple elements (they can be different inside of the same tuple), it can only provide you an Iterator[Any]. So you have to define a compare(Any,Any) function to handle what you want.