2.1.3 Immutable Sequences
Keywords: current

Next: 2.1.3.1 Linked Representation Up: 2.1 Sequences Previous: 2.1.2 Lists

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

Subsections

- 2.1.3.1 Linked Representation
- 2.1.3.2 Contiguous Representation