Keywords: current

Next: 2.1.6.1 Nested Classes vs. Up: 2.1 Sequences Previous: 2.1.5 List Containers

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

Subsections

- 2.1.6.1 Nested Classes vs. Inner Classes
- 2.1.6.2 Mutable Visitors

Next: 2.1.6.1 Nested Classes vs. Up: 2.1 Sequences Previous: 2.1.5 List Containers