1.6.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.5 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:

import java.util.*;
/** IntList := Empty + Cons */
abstract class IntList {

  /** returns first element of non-empty list 
   */
  abstract int getFirst();    

  /** returns all but the first element of non-empty list 
   */
  abstract IntList getRest();

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

class Empty extends IntList {

  int getFirst() { throw new NoSuchElementException(
    "getFirst invoked on Empty IntList");
  }
  IntList getRest() { throw new NoSuchElementException(
    "getRest invoked on Empty IntList");
  }

  public String toString() { return "()"; }
  String toStringHelp() { return ""; }
}

class Cons extends IntList {

  int first;
  IntList rest;

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

  int getFirst() { return first; }
  IntList getRest() { return rest;  }
 
  public String toString() {  // no leading space before first elt
    return "(" + first + rest.toStringHelp() + ")";
  }
  String toStringHelp() {    // leading space before each elt 
    return " " + first + rest.toStringHelp();  
  }
}

The three classes in the preceding program 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. The statement

import java.util.*;

on the first line is included in the program because the exception class NoSuchElementException is located in the library package java.util which is not automatically imported by the Java compiler. Only classes in the library package java.lang are automatically imported by the Java compiler. We will discuss exceptions in detail in Section 1.11.4. 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.

Finger Exercise: Copy the preceding IntList class into the Definitions window of DrJava and override the inherited definition of toString() to print the elements of an IntList. Test your code.

Optional Finger Exercise: Enclose the elements of a list in parentheses as they would be in Scheme. Hint: introduce a method toStringHelp() in the abstract class IntList to handle all internal (recursive) calls for conversion of an IntList to a String. If you are careful, you can even suppress generating any extra blanks (either before the first element or after the last element).

Let us compare the IntList defined above with the built-in lists of Scheme. Scheme provides the primitive operations empty, cons, first, and rest akin to the Java operations new Empty(), new Cons(...), getFirst(), and getRest() 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 of defining operations equivalent to the Scheme recognizers, because the isEmpty and isCons methods would only be applicable to objects of type IntList.