Quasi-Functional Lists

From the perspective of the public interfaces, quasi-functional lists differ from lists as containers in two respects. First, quasi-functional lists require the list arguments for setRest and set to be mutable list objects rather than immutable list values. Second, quasi-functional lists support visitor operations that mutate list structure in addition to the ``purely functional'' visitor operations corresponding to the SeqVisitor interface. To capture these differences in the Java type system, we introduce two new interfaces: a new mutable sequence interface called MutSeq:and a mutable visitor interface called MutSeqVisitor:

interface MutSeq extends Seq {
  void setFirst(Object f);         // changes this.first = f 
  void setRest(MutSeq r);          // changes this.rest = r
  void set(MutSeq m);              // changes this = m
  void setEltAt(int i, Object val);     // changes this[i] = val
  void insert(Object o);           // changes this.first,this.rest = o,this
  void remove();                   // changes this = this.rest
  Object execute(MutSeqVisitor m); // applies visitor operation m to this
}

interface MutSeqVisitor {
  Object forEmpty(MutSeq host);
  Object forCons(MutSeq host);
}

The MutSeq interface stipulates that the arguments to the operations setRest and set must be list objects, (objects of type MutSeq) rather than the list values (objects of type Seq) given in the SeqObject interface. The MutSeq interface also introduces an execute operation to support visitor operations (objects of type MutSeqVisitor) that mutate list structure. The MutSeqVisitor interface differs from the SeqVisitor interface in one key respect: the host object must be a mutable list (object of type MutSeq) rather than a list value (object of type Seq) enabling a visitor to destructively modify the host. This MutSeqVisitor interface is not applicable to lists as containers because the component rest fields embedded in the immutable list value are not mutable! The pivotal difference between the QuasiList and ListBox classes is the type of the rest field. A MutSeqVisitor can destructively modify both the first and rest fields of the host by using MutSeq mutator methods setFirst and setRest.

class QuasiList implements MutSeq {

  /* fields */  
  public static final Empty EMPTY = new Empty();

  private List value;

  /* constructor */
  QuasiList() { value = new Empty(); }
  private QuasiList(List v) { value = v; }

  /* visible methods */
  Seq empty() { return new QuasiList(); }
  Seq cons(Object newElt) { return new QuasiList(value.cons(newElt)); }
  Object first() { return value.first(); }
  Seq rest() { return value.rest(); }
  // rest returns a MutSeq (QuasiList) but the Seq interface mandates
  //   the weaker type!

  Object eltAt(int i) { return value.eltAt(i); }
  boolean isEmpty() { return value.isEmpty(); }
  void insert(Object o) { value = new Cons(o, new QuasiList(value)); }

  public String toString() { return value.toString(); }

  void setFirst(Seq v) { value = value.updateFirst(v); }

  void setRest(MutSeq m) { value = value.updateRest(m); }

  void set(MutSeq m) { value = m.value; }

  void setEltAt(int i, final Object val) {  
    /* inner class */
    class UpdateEltAt implements MutSeqVisitor {
      /* fields */
      final int index;       // index of element to be updated

      /* constructor */
      UpdateEltAt(int i) { index = i; }

      /* visit methods */
      Object forEmpty(MutSeq host) { throw
        new IllegalArgumentException("out-of-bounds index in UpdateEltAt");
      }
      Object forCons(MutSeq host) {
        if (index == 0) return host.setFirst(val);
        else return host.rest().execute(new UpdateEltAt(index-1));
      }
    }
    execute(new UpdateEltAt(i));  
  }

  void remove() { value = value.rest(); }

  Object execute(SeqVisitor v) { return value.execute(v); }
  // apply visitor v to value and return result; value is UNCHANGED

  Object execute(MutSeqVisitor v) { return value.execute(v,this); }
  // apply visitor v to value and return result; value may be CHANGED

  /* inner classes */
  private interface List {
    abstract String toStringHelp();
    // List -> String without any parentheses and leading blanks
  }

  private class Empty extends List {

    /* constructor */
    private Empty() {}  

    /* methods */
    Object first() { 
    throw new IllegalArgumentException("first() applied to empty list");
    }
    MutSeq rest() { 
    throw new IllegalArgumentException("rest() applied to empty list");
    }
    Object eltAt(int i) { 
      throw new IllegalArgumentException("out-of-bounds index in List.eltAt"); 
    }
    Object execute(SeqVisitor v) { return v.forEmpty(this); }
    Object execute(MutSeqVisitor v) { return v.forEmpty(QuasiList.this); }
    public String toString() { return "()"; }
    public String toStringHelp() { return ""; }
  }

  private class Cons extends List {

    /* fields */
    private final Object first;
    private final MutSeq rest;

    /* constructor */
    Cons(Object f, List r) {
      first = f;
      rest = r;
    }

    /* functional methods */
    Object first() { return first; }
    Seq rest() { return rest; }
    /* MutSeq is the correct output type but Java does not support it */

    Object eltAt(int i) { 
      if (0 == i) return first;
      else return rest.eltAt(i-1);
    }

    /* mutator methods */
    void setFirst(Object o) { first = o; }

    Object execute(SeqVisitor v) { v.forCons(this); }
    Object execute(MutSeqVisitor v) { v.forCons(QuasiList.this); }

    public String toString() { 
      return "(" + first + rest.toStringHelp() + ")"; }
    String toStringHelp() { return " " + first + rest.toStringHelp(); }
  } 

}

The QuasiList implementation given above uses the state pattern to represent each tail (rest component) of the list. Each tail is a quasilist object that can mutate between two forms: empty and non-empty. Since each tail is a mutable object supporting the state pattern, a MutSeqVisitor can modify the state of any tail in the process of traversing a list.

The QuasiList code uses inner classes to hide the classes implementing the state of a QuasiList and to eliminate passing the QuasiList host as an extra parameter to the execute(MutSeqVisitor v) methods in the Cons and Emtpy subclasses of List. If the List class is moved outside of QuasiList, the QuasiList object containing a given List object is not accessible to the List object.^2.4