Natural order for Pair and Triple

It is very useful to use ordered data structures such as TreeMap with Pair and Triple objects. In almost every other programming language, the natural order for tuples is the natural order of each element from left to right. For example in Python and Clojure:

sorted([[1, 2], [1, 5], [1, 1]])) => [[1, 1], [1, 2], [1, 5]]
(sort [[1 2] [1 5] [1 1]]) => ([1 1] [1 2] [1 5])

Even in statically typed languages such as C++ that happens as well (make_pair).

In Kotlin however, it is required to implement a cumbersome Comparable interface even when it is pretty clear what is the common case of sorting a Pair<Int, Int> for example. Is there any reason for that being the case?

The problem is that MutableList<T: Comparable<T>>.sort() requires the generic parameter to implement the Comparable interface. Pair however can only implement Comparable if both of it’s generic type parameters also implement it.

Thanks for the answer @Wasabi375. Technically Pair could always implement Comparable. When one of the generic type parameters doesn’t implement Comparable, then Pair could behave according of what you would expect in the case of a stable sort.

It is not how it works in statically typed language (C++ is a bad example because it violates typing in a lot of places in standard library). Using implicit defaults and fallbacks leads to a lot of errors. The correct way to do what you want in Kotlin is to define your own sort function:

fun List<Pair<Int,Int>>.sorted() : List<Pair<Int,Int>> = 
    sortedWith(
        Comparator{ a, b-> a.first().compareTo(b.first)}.thenBy{it.second()}
    )
1 Like

I’d like also advice creating separate one line types. From my point of view, it is better to use first code than second (however this is just opinion):

class Payment(val amount: Int, val currency: Currency)

val payments : List<Payment> = readPayments()
val payments : List<Pair<Int, Currency>> = readPayments()

I really appreciate all your answers. But I still can’t see how the limitation of providing a natural order for pairs is related to static typing. Here is a Haskell example:

import Data.List
sort [(1, 2), (1, 5), (1, 1)]
=> [(1,1),(1,2),(1,5)]

My example does exactly what you want it adds statically dispatched sort method exactly for your type. I think that Haskell does exactly the same. It is not possible to provide ordering rules for all possible types. You should either implement an interface (type-class) or add specific method for given type.

@darksnake your code is really nice and I am sure I will be using it in the future. I guess I am a bit surprised Kotlin doesn’t provide it out of the box for the basic types like the other programming languages. What I get from this thread is there is not enough motivation to provide that functionality as part of the standard library. Thanks to all for your answers!

I hope not. At least I didn’t want to make it sound that way. I was trying to explain why Pair can’t extend Comparable. Adding a function like @darksnake suggested (but generic) to the standard library is a completly different matter, which I think might be a good idea. I crated a feature request for it here: https://youtrack.jetbrains.com/issue/KT-36742

1 Like

That is really amazing, thanks for that @Wasabi375

Somehow I forgot about generics. It would look even simpler.

The version I put in the issue is

fun <A: Comparable<A>, B: Comparable<B>> List<Pair<A, B>>.sorted() : List<Pair<A, B>> =
    sortedWith(
    	Comparator<Pair<A, B>>{ a, b-> a.first.compareTo(b.first)}.thenBy{it.second}
    )
1 Like

I was also trying to solve the same issue but generalized to entire lists instead of just Pairs and I came up with the following solution in case someone find it useful in the future:

Haskell:

   import Data.List
   sort [[1, 1, 1, 2], [1, 1, 1, 5], [1, 1, 1, 1]]
=> [[1,1,1,1],[1,1,1,2],[1,1,1,5]]

Kotlin:

import java.util.Collections

class ComparableList<T:Comparable<T>>(vararg items: T): ArrayList<T>(items.asList()), Comparable<ComparableList<T>> {
    override fun compareTo(other: ComparableList<T>): Int {
      val limit = Math.min(this.size, other.size)
      for (i in 0 until limit) {
        if (this[i] > other[i]) return 1
        if (this[i] < other[i]) return -1
      } 
      return 0
    }
}

fun main() {    
    val sortedList = listOf(ComparableList(1, 1, 1, 2), ComparableList(1, 1, 1, 5), ComparableList(1, 1, 1, 1))
    Collections.sort(sortedList)
    println(sortedList)
} 

=> [[1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 1, 5]]

You don’t need an entire ComparableList class, you’re better off writing a Comparator that compares any two lists that contain compatible Comparables, or that takes an element-level Comparator.

1 Like