Generics design: Java and Scala

Java

"In contrast [to arrays], the subtyping relation for generics is invariant meaning that type List<S> is not considered to be a subtype of List<T> except in the trivial case where S and T are identical." [1] as a result, all of Java's collections are invariant.

So, why is there a hole in the type system that allows this to compile?

        List<Integer> ints  = Arrays.asList(1, 2, 3);
        boolean       found = ints.contains("a string");

of course ints cannot contain a String. You'll see the contains takes an Object.

"The designers of the Java libraries chose the first, more liberal, alternative, because someone using the Collections Framework before generics might well have written a test such as ints.containsAll
(objs), and that person would want that test to remain valid after generics were added to Java... Arguably, the library designers made the wrong choice." [1]

Scala

So, Scala must be smarter right? Let's take this class hierarchy:

class GrandParent { }
class Parent extends GrandParent { }
class Child extends Parent { }

And let's instantiate a few:

  val aGrandParent: GrandParent = new GrandParent
  val aParent:      Parent      = new Parent
  val aChild:       Child       = new Child

Now let's try

    val setOfParents:  Set[Parent] = Set(aParent)

    val setOfChildren: Set[Child]  = Set(aChild)

//    val contained = setOfChildren(aParent) // doesn't compile: type mismatch

    val contained                  = setOfParents(aChild)

So, we're stopped from asking if a set of children contains a parent object but we can still ask a set of parents if they contain child objects. That's better. So what about lists?

    val listOfParents:  List[Parent] = List(aParent)
    val listOfChildren: List[Child]  = List(aChild)

    listOfParents.contains(aChild)
    listOfChildren.contains(aParent)

Yikes - it's just as bad as Java.

The reason is straightforward (why I will explain later):

In the case of List, covariance was chosen, and List.contains takes Any.
In the case of Set, invariance was chosen, and Set.contains takes A.

The question remains: why was this design decision made?

To which Martin Odersky replied:

"On the issue of sets, I believe the non-variance stems also from the implementations. Common sets are implemented as hashtables, which are non-variant arrays of the key type. I agree it's a slighly annoying irregularity."

So, basically, a design decision in the cases of both Java and Scala.

[1] Java Generics, Naftalin and Wadler

Further reading:

1. the debate on StackOverflow.
2. Michael Payton Jones's blog.