What has been learned about making variance part of the type?

Question

In Java, the variance of parameterized types is indicated depending on how it's used:

<A extends B,B> void store(ArrayList<B> list, A elem) {
    list.add(elem);
}

Whereas in Scala it is indicated in the class declaration with a + or -.

What I want to know is, now that Scala has been around awhile, what has been people's experience with making variance a property of the type? Is it generally flexible enough for what you want to do? Are there aspects you would have done differently, knowing what you know now?

Answer 1

There is a lot of misunderstanding in the question:

First, there is no such thing as "variance of parametric types". Types (as List[Int]) are, by themselves, fixed, and therefore not variant (co-/contra-variant). What can be co(ntra)variant, are type constructors, eg. List, which are not themselves types.

Therefore, the line

<A extends B,B> void store(ArrayList<B> list, A elem)

cannot "indicate variance of types", since it does not define any type constructor. It is a simple example of (bounded) parametric polymorphism.

We have several types of polymorphism in programming languages. The one most natural to OOP languages like Java is subtype polymorphism, which is characterized by the fact that from X <: Y and t : Y, it follows that t : Y (IOW if a term/variable/parameter/whatever has type X which is a subtype of Y, it has also type Y and is usable in any place a real Y would be).

Another type of polymorphism is parametric polymorphism, which means that some types are actually type variables, which represent a placeholder for any type and are instantiated to real types during typechecking. Bounded parametric polymorphism means the tpe variables can be constrained to be a subtype or supertype of other type. Generics offer parametric polymorphism in Java.

Now, how do these two play together? It seems natural that a file of employees can be read as a file of citizen, since every employee is naturally a citizen (which is captured in the program by the subtype relation). This means ReadableFile[Employee] <: ReadableFile[Citizen]. However, the rules for determining subtypes don't support this conclusion - both types are totally unrelated.

This is where variance comes to play. If we define some type constructors (in this case ReadableFile) to be co(contra-)variant, we can use inference rules like "if X <: Y and T is covariant, then T[X] <: T[Y]". In effect, this rule supports the conclusion above.

Parametric type constructors in Java are always invariant.

As you have already noted, we can sometimes get away without variant type constructors and still achieve the same effect. In function parameters,

def foo(x : TCovar[Reader]) : Unit

with covariant TCovar is functionally equivalent to

def foo[A <: Reader](x : T[A]) : Unit

This doesn't anyhow mean that T in the second definition is covariant.

However, in function return type and variable types, this trick doesn't generally help. Even in that case, we can get the same effect as variant type constructors with the help of existential types. So

val foo : TCovar[Reader]

becomes

val foo : T[X] forSome { type X <: Reader }

You can see this in action in this example. As you can see in the definition of v4 and v5, covariant type constructors can make the program much simpler. This simplification applies to the function parameter declarations, too, which is why functional programming languages with subtype polymorphism use variant type constructors (at least for their function types).

However, for a type constructor to be covariant, it needs to satisfy some rules. These rules cause that Java's List<T> and other interfaces are actually invariant, because they provide both reading and writing of the container data (which is typical for imperative programming). Scala's functional data structures don't work that way, so they can be covariant. It is demonstrated in the example, too - NCov can't be covariant, because it provides read and write access to its inner data. I believe this is the main reason covariant type constructors don't exist in Java, which is the answer to your question.

Sorry for mixing Java and Scala in this post. I hope the examples are so easy to understand that it doesn't matter.

Answer 2

I know this is not really answers to your question, but they may trigger some other replies... :-)

---

I would like to suggest a different code. I have difficulties with a few points:

• type parameters are in reverse order (A is first, but depends on B)
• ArrayList is a strong type, List would make the code more general (reusable new, robust to future changes)

• I also like to have multiples objets (such as List) end with an 's'... :-)

  <A> void store(List<A> items, A item) {
    items.add(item);
  }
  

---

In Java, we also sometimes have the variable type, either as a parameter to a method or in a class. This is the part I can comment on.

As a method parameter, it has been useful for me in several situations:

• when the method needs to look into a map, to find an instance that depends on the actual class needed.

  Registry.java
    public <E> E find(Class<E> clazz){
      return (E) map.get(clazz);
      // The cast is fine, because it is how we store in the map.
    }
  

• To create an instance if needed.

  public <E extends Item> List<Item> singletonList(Class<E> itemClass){
      List<Item> items = ...;
      if (items.isEmpty()) {
        items.add(createDefaultInstanceFor(itemClass);
      }
      return items;
    }
  

As a class parameter, I use often :

• in Builders with inheritance (to make the last line work).

  ABuilder.java
  class ABuilder<E extends ABuilder> {
    private int size;
  
    public E withSize(int someSize) {
        size = someSize;
        return (E) this;
    }
  
  BBuilder.java
  class BBuilder extends ABuilder<BBuilder> {
     // here, no redefinition of method withSize
  
     public void onlyOnB(){
     }
  }
  
  Caller.java
    {
       BBuilder b = ...;
       b.withSize(2).onlyOnB();
       // The call still returns the subclass BBuilder, 
       // even though it is defined in the superclass ABuilder only.
    }