Behold the power of parametric polymorphism

Adding generic types to Java could mean less coding and fewer

By Eric Allen, JavaWorld.com, 02/01/00

What will the types of these fields be? Clearly, rest should be of type List. If you know in advance that your lists will always contain elements of a given class, the task of coding will be considerably easier at this point. If you know that your list elements will all be integers, for instance, you can assign first to be of type integer.

However, if, as is often the case, you don't know this information in advance, you must settle for the least common superclass that has all possible elements contained in your lists, which typically is the universal reference type Object. Hence, your code for lists of varying type elements has the following form:

abstract class List {
    public abstract Object accept(ListVisitor that);
}
interface ListVisitor {
    public Object _case(Empty that);
    public Object _case(Cons that);
}
class Empty extends List {
    public Object accept(ListVisitor that) {
      return that._case(this);
    }
}
class Cons extends List {
    private Object first;
    private List rest;
    
    Cons(Object _first, List _rest) {
      first = _first;
      rest = _rest;
    }
    
    public Object first() {return first;}
    public List rest() {return rest;}
    
    public Object accept(ListVisitor that) {
      return that._case(this);
    }
}

Although Java programmers often use the least common superclass for a field in this way, the approach has its disadvantages. Suppose you create a ListVisitor that adds all the elements of a list of Integers and returns the result, as illustrated below:

class AddVisitor implements ListVisitor {
    private Integer zero = new Integer(0);
    public Object _case(Empty that) {return zero;}
    public Object _case(Cons that) {
      return new Integer(((Integer) that.first()).intValue() + 
                     ((Integer) that.rest().accept(this)).intValue());
    }
}

Note the explicit casts to Integer in the second _case(...) method. You are repeatedly performing runtime tests to check properties of the data; ideally, the compiler should perform these tests for you as part of program type checking. But since you are not guaranteed that AddVisitor will only be applied to Lists of Integers, the Java type checker cannot confirm that you are, in fact, adding two Integers unless the casts are present.

You could potentially obtain more precise type checking, but only by sacrificing polymorphism and duplicating code. You could, for instance, create a special List class (with corresponding Cons and Empty subclasses, as well as a special Visitor interface) for each class of element you store in a List. In the example above, you would create an IntegerList class whose elements are all Integers. But if you wanted to store, say, Booleans in some other place in the program, you would have to create a BooleanList class.