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.4 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.
An IntList is either:
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. 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.9.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.
The IntList class includes the method toStringHelp as a ``help'' method for printing lists without any extraneous spaces. The String representation for every list is enclosed 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.