Comparing lists of comparables in Kotlin

Question

I'm trying to write a function that compares two lists of comparables. The comparables can be of various types as long as the elements at the same positions in the two lists being compared are comparable. Example:

    val list1 = ArrayList<Comparable<*>>()
    val list2 = ArrayList<Comparable<*>>()

    list1.add(10)
    list1.add("xyz")
    list1.add('a')

    list2.add(10)
    list2.add("xyz")
    list2.add('b')

    println(compare(list1, list2))

This should print -1 because

• 10 == 10
• "xyz" == "xyz"
• 'a' < 'b'

and thus list1 < list2.

Here's the code that I have put together with a bit of a trial and error process since I'm a little bit confused about how generics work in this specific case:

fun <T> compare(list1: List<Comparable<T>>, list2: List<Comparable<T>>): Int {
    for (i in 0..Math.max(list1.size, list2.size) - 1) {
        val elem1 = if (i < list1.size) list1[i] else null
        val elem2 = if (i < list2.size) list2[i] else null

        if (elem1 == null && elem2 == null)
            return 0

        if (elem1 == null)
            return -1

        if (elem2 == null)
            return 1

        @Suppress("UNCHECKED_CAST")
        val comparisonResult = elem1.compareTo(elem2 as T)

        if (comparisonResult != 0)
            return comparisonResult
    }

    return 0
}

And this actually compiles and works as expected, but there are a few things that I'm puzzled about.

My first attempt was with the following method signature:

fun compare(list1: List<Comparable<*>>, list2: List<Comparable<*>>): Int

This did not compile though. Why is that? And how is this declaration different from the other one?

Second, if I try comparing lists with incomparable values at the matching positions, I get a type cast error. For example, when comparing [1,1] to [1,"abc"], I get

java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

This apparently arises at the type cast in

elem1.compareTo(elem2 as T)

What puzzles me: How is the T resolved to Integer here? In fact, I'm surprised that this actually compiles.

And third, is there a way to get rid of the unchecked cast? I tried

if (elem2 !is T)
    // throw Exception

but that did not compile. Why? It seems that somehow it's known that T is meant to be Integer in this iteration, so why can't I type-check against it?

Answer 1

Comparable is an interface contravariant to its type parameter T. Values of type T are only allowed at in-positions, namely as parameters of class methods and not as return values.

interface Comparable<in T> {
    abstract operator fun compareTo(other: T): Int
}

A star-projection of contravariant type is equivalent to that type parametrized with Nothing, thus Comparable<*> is actually a Comparable<in Nothing>. It means that once you have a Comparable of unknown type, you cannot safely compare it to anything except a value of Nothing type, which is known to have no values. :)

You can encounter the consequence of such unsafety if you try to compare an Int with a String. It's not the elem2 as T throws ClassCastException (it is really an unchecked cast as the warning you have suppressed states), it's the implementation of String.compareTo who throws, when it meets something that isn't a String.

Returning back to the question, you can implement such list comparison with help of the library function kotlin.comparisons.compareValues. It knows how to handle nulls and hides nasty unchecked cast inside.

import kotlin.comparisons.*

fun compareLists(list1: List<Comparable<*>>, list2: List<Comparable<*>>): Int {
    for (i in 0..Math.min(list1.size, list2.size)-1) {
        val elem1 = list1[i]
        val elem2 = list2[i]

        if (elem1.javaClass != elem2.javaClass) {
            TODO("Decide what to do when you encounter values of different classes")
        }

        compareValues(elem1, elem2).let {
            if (it != 0) return it
        }
    }
    return compareValues(list1.size, list2.size)
}

Note, due to the type erasure in generics ensuring values have the same class (elem1.javaClass == elem2.javaClass) doesn't necessary mean the values could be safely compared. For example List<Int> and List<String> both have the same class List.