2.1.7 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 quasi-functional lists rather than immutable list values. Second, quasi-functional lists support visitor operations that mutate list structure in addition to the ``purely functional'' operations. To capture these differences in the Java type system, we introduce a new visitor interface QuasiListVisitor similar to SeqVisitor

interface QuasiListVisitor {
  Object forEmpty(QuasiList host); 
  Object forCons(QuasiList host);
}

where QuasiList a class defining quasi-functional lists. The QuasiList suppports the usual functional operations on lists plus mutators to change either the entire contents of the list (set), the first element or the list (setFirst), or the rest of the list (setRest). It is possible to use an interface for quasi-functional lists instead of QuasiList and avoid binding the type of the ``for'' method arguments in QuasiListVisitor to a specific class, but this generalization significantly complicates the implementation of quasi-functional lists. See the optional Challenge Exercise at the end of this subsection.

The following QuasiList contains a very simple implementation of quasi-functional lists. The pivotal difference between the QuasiList and ListBox classes is the type of the elts field. A QuasiListVisitor can destructively the contents of the host because the object stored in elts field is mutable. If that object is a non-empty list, then a visitor can modify both the first and rest fields of the host by using the QuasiList mutator methods setFirst and setRest.

import java.util.*;
 
interface QuasiListVisitor {
  Object forEmpty(QuasiList host);
  Object forCons(QuasiList host);
}

class QuasiList {

  private List elts;

  QuasiList() { elts = new Empty(); }
  private QuasiList(List v) { elts = v; }

  public String getFirst() { return elts.getFirst(); }
  public QuasiList getRest() { return elts.getRest(); }
  public String toString() { return elts.toString(); }
  public String toStringHelp() { return elts.toStringHelp(); }

  /* mutators */
  
  public void set(QuasiList ms) { elts = ms.elts; }
  public void setFirst(String v) { elts.setFirst(v); }
  public void setRest(QuasiList that) { elts.setRest(that); }
  public void insertFront(String v) { elts.insertFront(v, this); }
  public void removeFront() { elts.removeFront(this); }
  public Object apply(QuasiListVisitor v) { return elts.apply(v, this); }

  /* inner classes */

  /** internal state class for QuasiList elts */
  private static abstract class List {
      
    abstract String getFirst(); 
    abstract QuasiList getRest(); 
    abstract String toStringHelp();
 
    abstract void setFirst(String s);
    abstract void setRest(QuasiList that);
    abstract void insertFront(String s, final QuasiList owner);
    abstract void removeFront(QuasiList owner);
    abstract Object apply(QuasiListVisitor v, final QuasiList owner);
  }
    
  private static class Empty extends List {
    
    /* relying on default constructor */
    static Empty only = new Empty();

    public String getFirst() { throw 
      new NoSuchElementException("first() applied to empty list");
    }
    public QuasiList getRest() { 
      throw new NoSuchElementException("rest() applied to empty list");
    }
    public String toString() { return "()"; }
    public String toStringHelp() { return ""; }

    /* mutators */
    public void setFirst(String s) { throw 
      new NoSuchElementException("setFirst() applied to empty list");
    }
    public void setRest(QuasiList ms) { throw 
      new NoSuchElementException("setRest() applied to empty list");
    }

    public void insertFront(String v, final QuasiList owner) { 
      owner.elts = new Cons(v, new QuasiList(owner.elts)); 
    }

    public void removeFront(final QuasiList owner) { throw
      new NoSuchElementException("removeFront() applied to empty list");
    }

    public Object apply(QuasiListVisitor v, final QuasiList owner) { 
      return v.forEmpty(owner); 
    }
  }

  private static class Cons extends List {
    
    private String first;
    private QuasiList rest;

    Cons(String f, QuasiList r) {
      first = f;
      rest = r;
    }

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

    /* mutators */
    public void setFirst(String v) { first = v; }
    public void setRest(QuasiList ms) { rest = ms; }

    public void insertFront(String v, QuasiList owner) { 
      owner.elts = new Cons(v, new QuasiList(owner.elts)); 
    }
    public void removeFront(QuasiList owner) { owner.set(rest); }
     
    public Object apply(QuasiListVisitor v, QuasiList owner) { 
        return v.forCons(owner); }
  } 
}

The QuasiList class uses the state pattern to represent the contents of the list--and, recursively, the contents of each tail (rest) of the list. The elts field of a a QuasiList object that can mutate between two forms: empty (Empty) and non-empty (Cons). Since each tail is a QuasiListVisitor supporting the state pattern, a QuasiListVisitor 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.

Challenge Exercise Define an interface QuasiListI for quasi-functional lists and modify the QuasiListVisitor interface to use this interface instead of the QuasiList class. Modify the implementation of the QuasiList class so that it implements the QuasiListI interface. Hints: (i) the rest field in the hidden inner Cons class must have type QuasiListI and (ii) the the set operation requires a more complex implementation because an object of type QuasiListI does not necessarily have an elts field of type QuasiList.List. Thoroughly test your code.