1.5.2 An Extended Example: Lists
Keywords: current

Next: 1.5.3 Singleton Pattern Up: 1.5 Basic Program Design Previous: 1.5.1.6 Test

##
1.5.2 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.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:

- 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. 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`.

Next: 1.5.3 Singleton Pattern Up: 1.5 Basic Program Design Previous: 1.5.1.6 Test