2.1.3 Immutable Sequences

An immutable sequence type Seq with elements of type T supports some subset of the following operations on a Seq object this representing s₀, s₁, ..., s_n, n>=0:

/** represents a possibly empty sequence of elements 
 *  s[0], s[1], ..., s[n] of type T 
 */
interface Seq {
  /** returns the empty sequence */
  Seq empty();

  /** returns a Seq with elements newElt, s[0], ..., s[n] */
  Seq cons(T newElt);

  /** returns the element s[0] */
  T first();

  /** returns a Seq with elements s[1], ..., s[n] */
  Seq rest();

  /** returns the element s[i] */
  T eltAt(int i); 

  /** returns true if this is empty */
  boolean isEmpty();

  /** applies the visitor to host */
  public Object apply(SeqVisitor host);  
}

interface SeqVisitor {
  Object forEmpty(Seq host);
  Object forCons(Seq host);
}

Unfortunately, Java does not yet support the parameterization of interface and class definitions by type. In all of our sample code involving sequences, the element type T must be replaced by a specific type such as Object appropriate for the intended application.

The SeqVisitor interface is similar to the Visitor interface that we defined for arithmetic expressions, but there is a very important, subtle difference. The SeqVisitor is designed to work with any class implementing the Seq interface. It makes no assumptions about the underlying representation of sequences. In contrast, the Visitor interface for arithmetic expressions was designed on the assumption that arithmetic expressions are represented by a composite hierarchy of classes. This difference is evident in the type declarations for the host argument in the for... methods. In the Visitor interface, each for... method has a different concrete variant as the host type. In the SeqVisitor interface, all of the for... methods have the same host type, namely Seq.

Neither of these two approaches to formulating visitor interfaces is uniformly better than the other one. The concrete version that we used for arithmetic expressions has more precise type declarations and catches more programming errors. The abstract version used in Seq is more flexible and accommodates multiple implementations.