About generics in Java and Scala

Question

I am confused by the generic subtyping.

In Java, if type A is a subtype of B, generic type C<A> and C<B> are invariant. For instance, ArrayList<Base> is not a subtype of ArrayList<Derived>.

However, in Scala, generic type C<A> and C<B> are covariant if type A is a subtype of B. So what's the property of generic class in Scala has but not in Java?

Holozoic

I don't really understand what your question means. – Asgard

In Scala we write C[A] and C[B], and no, they are not subtypes of one another by default. Only if you declare C as class C[+T], and the compiler will let you do that if T only appears in covariant positions in C. – Noticeable

@OliCharlesworth In conclude, my question is if type A is a subtype of B and generic type C[A] is also the subtype of C[B], what the property of such generic type has? – Holozoic

@n.m. Thanks for correcting about the syntax. You are correct for the explanation of class C[+T]. – Holozoic

@user1391576: Your question says:ArrayList<Base> is not a subtype of ArrayList<Derived> but I guess what you want to ask is ArrayList<Derived> is not a subtype of ArrayList<Base>, don't you? – Baillargeon

Answer 1

Firstly note that variance is a property of generic type parameters, not of the parameterized types themselves.

Secondly: you are wrong about scala - type parameters are invariant by default. Let us investigate!

Java

Java has use-site variance annotations. That is, you can declare methods like this:

boolean addAll(Collection<? extends T> c);

There is, however, one form of "parameterized type" (I use the term loosely) in which the type parameters are covariant: Java Arrays! (This is actually insane because Arrays are mutable and hence it is easy to circumvent the type system). Consider the following:

public static void subvert(Object[] arr) { arr[0] = "Oh Noes!"; }

And then:

Integer[] arr = new Integer[1];
subvert(arr); //this call is allowed as arrays are covariant
Integer i = arr[0];

A good interview question this one: what happens?

Scala

In Scala, you have declaration-site variance. That is, the variance of a type parameter is declared alongside the parameter (using the annotations + and -):

trait Function1[-I, +O]

This says that the trait Function1 has two type parameters, I and O which are contra- and co-variant respectively. If no +/- annotation is declared, then the type parameter is invariant. For example, Set is invariant in its type parameter:

scala> def foo(set: Set[Any]) = ()
foo: (set: Set[Any])Unit

scala> Set(1)
res4: scala.collection.immutable.Set[Int] = Set(1)

scala> foo(res4)
<console>:10: error: type mismatch;
 found   : scala.collection.immutable.Set[Int]
 required: Set[Any]
Note: Int <: Any, but trait Set is invariant in type A.
You may wish to investigate a wildcard type such as `_ <: Any`. (SLS 3.2.10)
              foo(res4)
                  ^

List is however, declared as being covariant:

scala> def bar(list: List[Any]) = ()
bar: (list: List[Any])Unit

scala> List(1)
res6: List[Int] = List(1)

scala> bar(res6)

Why not ask the compiler?

Another way of demonstrating this is to ask the compiler directly for subtype-evidence:

scala> class Cov[+A]
defined class Cov

scala> implicitly[Cov[Int] <:< Cov[Any]]
res8: <:<[Cov[Int],Cov[Any]] = <function1>

But with an invariant type parameter

scala> class Inv[A]
defined class Inv

scala> implicitly[Inv[Int] <:< Inv[Any]]
<console>:9: error: Cannot prove that Inv[Int] <:< Inv[Any].
              implicitly[Inv[Int] <:< Inv[Any]]
                        ^

Lastly, contravariance:

scala> class Con[-A]
defined class Con

scala> implicitly[Con[Any] <:< Con[Int]]
res10: <:<[Con[Any],Con[Int]] = <function1>

See also identifier <:<

Economically