An Extended Example: Lists

Let us study how the design recipe described above applies to the process of writing some simple programs involving lists of integers. Lists are ubiquitous in programming. The DeptDirectory type introduced in Section 1.6 is simply a specialized form of list. For reasons that will become clear later in the monograph, we will use the name IntList rather than List for our list type. As you should recall from Scheme background, a IntList is either:

• an Empty list, or
• a composite list Cons(e,l) where e is the first Object of the IntList, and l is the rest of the IntList.

Compare this definition with the definition of DeptDirectory given earlier.

We can abbreviate the preceding definition using the following mathematical notation:

IntList := Empty() + Cons(int, IntList)

which states that the set IntList is the union of the sets Empty and Cons. The set Empty contains a single object Empty() while the set Cons contains all objects Cons(o,l) where o is any int and l is any element of type IntList.

Assume that we are given the task of writing a program to perform some standard operations on lists of integers such as computing the sum of the numbers in a list, computing the product of the numbers in a list, and sorting the members of a list into ascending order.

Since we need to perform a variety of different operations on IntList, we will include a full set of getter operations (also called selectors or accessors), namely getFirst and getRest methods corresponding to first and rest in Scheme. The following collection of Java classes provides a minimalist definition for the IntList type:

/** Composite Data Definition: 
 *  IntList := new Empty() + new Cons(int, IntList)
 */
abstract class IntList {

  /** Returns first element of non-empty list.
   *  Throws an IllegalArgumentException on Empty.
   */ 
  abstract int getFirst();    

  /** Returns the ``rest'' a non-empty list (all elements but first).
   *  Throws an IllegalArgumentException on Empty.
   */
  abstract IntList getRest();

  /** Returns "" for Empty
   *          " e1 e2 ... en" for IntList with elts e1,...,en
   */
  abstract String toStringHelp();  
}

class Empty extends IntList {

  /** The only instance of class Empty */
  static final Empty ONLY = new Empty(); // singleton pattern

  /* constructor */
  private Empty() {} 

  /* Cons accessors */  
  int getFirst() { throw new IllegalArgumentException(
   "first requires a non Empty IntList");
  }

  IntList getRest() { throw new IllegalArgumentException(
   "rest requires a non Empty IntList");
  }

  /* other methods */
  public String toString() { return "()"; }
  String toStringHelp() { return ""; }
}

class Cons extends IntList {

  /* private fields */
  private int first;
  private IntList rest;

  /* constructor */
  Cons(int f, IntList r) {
    first = f;
    rest = r;
  }

  /* accessors */
  int getFirst() { return first; }
  IntList getRest() { return rest;  }

  /* other methods
  public String toString() {  // no leading space before first
    return "(" + first + rest.toStringHelp() + ")";
  }
  String toStringHelp() {     // leading space before each elt 
    return " " + first + rest.toStringHelp();  
  }
}

These three classes form a conventional composite class hierarchy with IntList at the top. These class definitions rely on Java exceptions to handle erroneous uses of the getFirst and getRest methods. We will discuss exceptions in detail in Section 1.12.3. For now, all you need to know is that (i) all exceptions are elements of the the built-in type Exception and (ii) the throw statements in the bodies of getFirst and getRest in class Empty abort the computation and print the specified strings as part of the error message. Their meaning in this context produces exactly the same results as invoking the Scheme construct error.

The IntList class includes the method toStringHelp() as a ``help'' method for printing lists with exactly the same spacing as in Scheme. The String representation for every list is enclosing in parentheses, but leading blanks appear every element after the first. The toStringHelp() method is responsible for printing the elements of a list tail that excludes the first element. Hence, toStringHelp() generates a space before each element that it processes. In contrast, toString() generates the enclosing parentheses and the first element if present; it delegates formatting the remaining elements of the list to toStringHelp().

Let us compare the IntList defined above with the built-in lists of Scheme. Scheme provides the primitive operations empty, cons, getFirst, and getRest akin to the Java operations new Empty(), new Cons(...), first, and rest. Scheme also provides recognizers for empty and compound lists called empty? and cons? which have no visible analog in the preceding Java program. We could try to define analogous operations in our Java data definition by including abstract boolean operations isEmpty and isCons in the abstract class IntList and define them appropriately in the concrete subclasses Empty and Cons. But this approach does not achieve our objective or defining operations equivalent to the Scheme recognizers, because the isEmpty and isCons methods are applicable only to objects of type IntList.