2.1.5 List Containers
Keywords: current

Next: 2.1.6 Quasi-Functional Lists Up: 2.1 Sequences Previous: 2.1.4.1 Singly-linked Mutable List

##
2.1.5 List Containers

A better approach is to define a container class with a single field that holds an immutable sequence. Then we can update the mutable sequence by modifying the contents of the field in the container object. For example, suppose we have a class `List` that defines a list representation for immutable sequences. The following container class works for any implementation of the `Seq` interface:

    class ListBox implements SeqObject {

      private static Seq prototype = new ...;
      // any instance of the class implementing Seq

      /* fields */
      private Seq value;  // contents of ListBox: s[0],s[1],...,s[n-1]

      /* constructors */
      ListBox() { value = prototype.empty(); }
      ListBox(Seq v) { value = v; }

      /* visible accessor methods */
      public Seq empty() { return new ListBox(); }
      public Seq cons(Object newElt) { return new ListBox(value.cons(newElt)); }
      public Object first() { return value.first(); }
      public Seq rest() { return value.rest(); }
      public Object eltAt(int i) { return value.eltAt(i); }
      public boolean isEmpty() { return value.isEmpty(); }

      /* visible mutator methods */
      public void setFirst(Object o) { value = value.updateFirst(o); }
      public void setRest(Seq r) { value = value.updateRest(r); }
      public void set(Seq v) { value = v; }  // set contents of box to v;

      public void setEltAt(int i, final Object val) {  // changes s[i] to val
        return execute(new UpdateEltAt(i), val);
      }

      public void insert(Object o) { value = value.cons(o); }
      // changes contents of this from s[0],...,s[n] to o,s[0],...,s[n]

      public void remove() { value = value.rest; }  // removes s[0] from the sequence

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

      /* inner classes */
      private class UpdateEltAt implements SeqVisitor {
        /* fields */
        int index;          // index of element to be updated
        Object eltValue;    // new value for updated element

        /* constructor */
        UpdateEltAt(int i, Object e) { index = i; eltValue = e; }

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

The variable holding the `Seq` instance is now wrapped inside an instance of a class (`ListBox` above) implementing the `SeqObject` interface. A method that accepts a `SeqObject` as an argument can modify it.

In the preceding example, the use of the inner class `UpdateEltAt` warrants careful study. This inner class is a private member of the `ListBox` class and hence inaccessible outside of the class body. Since the inner class referenced only within the `setEltAt` method, we could have placed the definition of `UpdateEltAt` as a declaration inside the body of this method! In this case, the `UpdateEltAt` class would have been visible only within the method `setEltAt` But such an embedded inner class definition can be hard to read, so we elected to make a private member of the `ListBox` instead.

We have already seen a special case of inner classes, namely anonymous classes that appear inside dynamic methods. The only difference between an inner class and a conventional class is that every instance of an inner class has an enclosing instance of the class `C` that textually contains its definition. The free variables in the inner class refer to this class. In addition, the notation `C.this` refers to the ``entire'' enclosing instance. Inner classes impose exactly the same restrictions on references to local variables of the enclosing instance as anonymous classes do: any such local variable must be declared `final`. Inner classes are discussed in more detail in Section 2.1.6.

In `ListBox` class, the methods `insert`, `remove`, and `set` modify the receiver of the method invocation, so there is no need for them to return values. Consequently they have return type `void`. Mutator methods typically have the return type `void` because they embody commands that modify objects rather than functions that compute new values based on the value of `this`.

The ``lists as containers'' representation of mutable lists is a very simple example of the `state` pattern. In the state pattern, a mutable object contains a field of union type (denoted by an abstract class or interface) representing the state of the object. The object can easily change ``shape'' by updating the field to contain an instance of a different class in the union. In the `ListBox` class, an empty list object can mutate to a non-empty list object (or vice-versa) by modifying the contents of the `value` field containing a `Seq`, which is a union type.

Since the `SeqObject` interface extends the `Seq` interface, it inherits the visitor interface from the immutable `Seq` interface. As a result, no visitor class implementing the `SeqVisitor` interface can mutate a `SeqObject`! In particular, to mutate fields of a `ListBox` object, we must use explicit assignment. Given a `ListBox l` and `SeqVisitor v` that returns a `ListBox`, the assignment

> `l = (ListBox) l.execute(v);`

updates `l` to the new value returned by the visitor operation.

The efficient operations on `ListBox` objects are precisely the efficient operations on the underlying functional `List` class, namely, adding and removing elements at the front of the list. Mutable lists in which elements can only added or removed at the front are called stacks or LIFO ("last in, first out") lists. Representing mutable lists as containers holding immutable list values is well-suited to this form of usage. The operations `first`, `insert`, and `pop` precisely match the usual operations `push`, `top`, and `pop` on stacks.

The ``container'' representation for mutable lists is simple and easy-to-use but it is poorly suited to many applications because it fails to support certain list operation efficiently. This representation forces list nodes (Cons objects) to be recopied whenever the list is changed. To modify the list element with index i or insert and element in front of the list element with index i, a computation must construct a new `List`, copying the elements from the old `List` with indices less than i. We can avoid this recopying process and avoid the potentially confusing distinction between immutable list values and mutable list objects by using a mutable variant of functional lists developed by Dung Nguyen and Steve Wong.

Next: 2.1.6 Quasi-Functional Lists Up: 2.1 Sequences Previous: 2.1.4.1 Singly-linked Mutable List