Natural order for Pair and Triple

Language Design
1

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?

2

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.

3

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.

4

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
5

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

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

7

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.

8

@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!

9

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
10

That is really amazing, thanks for that @Wasabi375

11

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

12

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
13

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]]
14

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
15

Thank you @derektom14. My attempt with ComparableList was easier because that class ended up being Comparable. However, when I try to implement your suggestion, I get some issues because List is not Comparable, so I am not sure how can I provide a generic comparator for the nested lists.

The following code works if I change List<T:Comparable<T> by List<Int>:

val comp = Comparator<List<Comparable<T>>> { a: List<Comparable<T>>, b: List<Comparable<T>> -> 
      var r = 0
      val limit = Math.min(a.size, b.size)
      for (i in 0 until limit) {
        if (a[i] > b[i]) r = 1
        if (a[i] < b[i]) r = -1
      } 
      r
}

val list: MutableList<List<Int>> = mutableListOf(listOf(1, 1, 1, 2), listOf(1, 1, 1, 5), listOf(1, 1, 1, 1))
println(list.sortedWith(comp))
16

Rather than a generic comparator, how about an extension that returns an appropriate comparator?

In other words… list.sortedWith(list.comparator()).

I haven’t tried implementing it, but it seems like you could make something using an inline extension with a reified generic parameter.

Because List doesn’t implement Comparable, you may need to defined extensions for List<Comparable<T>> and List<List<Comparable<T>>> etc. but those can be defined in a library, so as not to clutter up your general code.

Another thought: Rather than defining this on list, how about making it work for any Iterable<Comparable<T>>?

The code is a little more complex (you need to make iterators for both) but if it’s going in a library it’s hidden away anyway, and this adds a lot more flexibility. Something like (untested)…

        override fun compare(a: Iterable<T>, b: Iterable<T>) : Int {
            val aIter = a.iterator()
            val bIter = b.iterator()
            while( aIter.hasNext() && bIter.hasNext() )
                aIter.next().compareTo(bIter.next()).let{ if(it!=0) return it }
            return when {
                aIter.hasNext() -> 1
                bIter.hasNext() -> -1
                else -> 0
            }
        }
17

@ryepesg you’ll need to indicate that T : Comparable<T>, like this:

fun <T : Comparable<T>> listComparator(): Comparator<List<T>> = Comparator<List<T>> { a: List<T>, b: List<T> -> 
      var r = 0
      val limit = Math.min(a.size, b.size)
      for (i in 0 until limit) {
        if (a[i] > b[i]) r = 1
        if (a[i] < b[i]) r = -1
      } 
      r
}

val list: MutableList<List<Int>> = mutableListOf(listOf(1, 1, 1, 2), listOf(1, 1, 1, 5), listOf(1, 1, 1, 1))

println(list.sortedWith(listComparator()))

You could potentially reuse the same Comparator object for all calls to listComparator, casting it with an unchecked cast, though you’d have to do some testing to be confident that that would work.

18

Thanks a lot @derektom14 and @naxymatt, the following code works like a charm:

fun <T:Comparable<T>> comparator() = Comparator<List<T>> { a: Iterable<T>, b: Iterable<T> ->
  val aIter = a.iterator()
  val bIter = b.iterator()
  var r = 0
  while(aIter.hasNext() && bIter.hasNext())
    aIter.next().compareTo(bIter.next()).let { if(it != 0) r = it }
  when {
    aIter.hasNext() -> 1
    bIter.hasNext() -> -1
    else -> r
  }
}