Translating generic wildcards from Java to Scala

Question

In the java.util.Collections class, we have two variants of the sort method, one that takes a list of arbitrary objects with a corresponding Comparator:

public static <T> void sort(List<T> list, Comparator<? super T> comparator)

And one that takes a list of Comparable objects:

public static <T extends Comparable<? super T>> void sort(List<T> list)

---

I was thinking how one woulds translate such method signatures with bounded wildcards into Scala. For the first version, I translated the signature literally and at first sight without compilation problems:

def sort[T](list: List[T], comparator: Comparator[_ >: T]) { ??? }

But then I found that I could not invoke this method with the following arguments:

val comparator = new Comparator[Object] {
    def compare(o1: Object, o2: Object) = ???
}
val list = new ArrayList[Number]
sort[Object](list, comparator)

The last line gives this compile error, even though I explicitly specify the type T as Object.

type mismatch; found : java.util.ArrayList[Number] required: java.util.List[Object] Note: Number <: Object, but Java-defined trait List is invariant in type E. You may wish to investigate a wildcard type such as _ <: Object. (SLS 3.2.10)

Actually, I found out that it's even impossible to call the sole Java method directly as it fails with the same type of error.

Collections.sort[Object](list, comparator)

---

As for the version with comparable list, I came up with this declaration:

def sort[T <: Comparable[_ >: T]](list: List[T]) { ??? }

But this doesn't work at all:

illegal cyclic reference involving type T

---

What am I doing wrong? Are Scala variant generics following different rules the the Java ones? How call one call the Collections.sort method without actually getting a compile error?

Side note:

No, I'm not really asking how I can sort a list in Scala. I know that Scala has its own set of collections, sort functions and a different approach to comparing objects (such as Ordered and Ordering traits). My question concerns the general problem of generic methods and translation of generics from Java to Scala.

Answer 1

You are giving the wrong type parameter for T: You sort a List[Number], not a List[Object]:

sort[Number](list, comparator)

will work.

If you want to call sort without a type argument, you need to define two argument lists (because of how type-inference works in Scala):

def sort[T](list: List[T])(comparator: Comparator[_ >: T]) { ??? }

// Then
sort(list)(comparator)

You might want to consider using Scala types, that have proper support for covariance (i.e. in Scala a List[Number] is a List[Object]).

Concerning the version with comparable, you'll have to explicitly write the wildcard:

def sort[T <: Comparable[T], U <: T](list: List[U]) { ??? }

Answer 2

You could call the Java variant (or yours) with:

Collections.sort[Number](list, comparator)

The problem here is because Java generic types are invariant. In other words, this fails in Java:

List<Number> l1;
List<Integer> l2 = l1; //contravariance fails
List<Object> l3 = l1; //covariance fails

In Scala, generic type parameters can be declared to be covariant or contravariant in their declaration. Scala's List type parameter is declared to be covariant (which works because it's immutable). In other words, this is valid:

val l1: List[Number] = ???
val l2: List[Object] = l1 //valid

But since you're using Java's java.util.List that's not an option.