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.

Daniel C. Sobral · Accepted Answer · 2012-06-19T23:08:24.227

29

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.

edited Jun 19 '12 at 23:08

answered Jun 19 '12 at 15:41

Daniel C. Sobral

295,120
86
501
681

Good points, Daniel. I have edited my question to state compared tuples always have the same arity. As for non-ordered types, my tuples should have symbols (that's the reason I went for tuples instead of lists), but because I have not found any way of ordering symbols, I will, instead, use numbers. Should I be using lists then? What if I really needed to add symbols to the list? – lasaro Jun 19 '12 at 20:25
1

@lasaro Well, now that you simplified the problem, there's a relatively easy solution. See edited answer. – Daniel C. Sobral Jun 19 '12 at 23:09
Thanks Daniel, for you very concise example. – lasaro Jun 20 '12 at 12:38
1

This doesn't appear to work in 2.11.8, but does if you `import scala.math.Ordered.orderingToOrdered` as suggested https://stackoverflow.com/questions/19345030/easy-idiomatic-way-to-define-ordering-for-a-simple-case-class – Moodragonx Jul 07 '17 at 03:39

score 14 · Answer 2 · answered Sep 05 '12 at 22:03

14

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.

answered Sep 05 '12 at 22:03

schmmd

18,650
16
58
102

Heinzi · Answer 3 · 2012-06-19T14:09:16.883

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.

You could possibly enable `-Xexperimental` which will choose the LUB instead of `Any`. — soc, Jun 19 '12 at 15:32
Thanks Heinzi, for your complete answer. I learned a lot from it, but for the level of my question and scala skills, Daniel's was more to the point. — lasaro, Jun 20 '12 at 12:40

How to lexicographically compare scala tuples?

3 Answers3

Linked