2.1.3 Immutable Sequences

All of the sequence classes presented in this monograph--immutable and mutable--support the operations in the following Seq interface

interface Seq {
  Seq empty();
  // returns Seq that is empty

  Seq cons(Object newElt);
  // returns the Seq with elts newElt, s[0], ..., s[n]

  Object first();     // returns the element s[0]
  Seq rest();         // returns an object representing s[1], ..., s[n]
  Object eltAt(int i);  // returns the element s[i]
  boolean isEmpty();    // returns n == 0  

  public Object execute(SeqVisitor host);  // applies the visitor code host
}

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

The contracts for all of these operations stipulate that they do not modify the observable state of a sequence object.

Immutable sequence classes also support the two additional functional operations in the following interface:

interface FinalSeq extends Seq {
  Seq updateFirst(Object val);  // returns val,this[1], ...,this[n]
  Seq updateRest(Seq r);   
  // given r[0],...,r[m] returns this[0],r[0], ..., r[m]
}

These two operations return new sequence values; they do not modify this.

There are two widely used representations for immutable sequences: linked and contiguous.