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.