How to lexicographically compare scala tuples?

Question

Given two tuples of the same clarity, how can I compare them with lexicography? It seems like it should be as simple as in the next snippet, but it is not. Any simple example of how to do this?

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

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

Answer 1

It’s not easy, because for now

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

looks pretty simple

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

no. How do you feel about non-ordered types? How do you feel about different types in the same tuple position?

Do you provide that all types are the same? In this case, you do not have a tuple. The whole essence of the 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 ran into this problem - and I would try very hard not to do this - I would capture Shapeless, turn tuples into something like HLists, and then try to compare this.

EDIT

And now it’s a lot easier:

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

These additional implications are not automatically available, as in some cases they can lead to vague implications.

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)) 

The orders for all tuples with comparable parts are defined.

Answer 3

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

Another way would be: extend the tuple class to <statement via implicit listing:

 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 other comparison operators, you can 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 the documentation ) and allows you to get an iterator over a tuple. This way you can write a function as if you did it with a list.

Edit3: It will be something like this:

 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 need to take care of the types. Since the function does not know the types of elements of the tuple (they can be different within the same tuple), it can provide only Iterator [Any]. Therefore, you need to define a comparison function (Any, Any) to handle what you want.