/** Data Definition: IntList :=  new Empty() + new Cons(int, IntList) */

interface IntList {
  /** Returns the empty list. */
  IntList empty();
  /** Adds i to the front of this. */
  IntList cons(int i);
  /** Returns String representation of this without enclosing parens. */
  String toStringHelp();
}

abstract class EmptyConsCode implements IntList {
  public IntList empty() { return Empty.ONLY; }
  public IntList cons(int i) { return new Cons(i, this); }
}

class Empty extends EmptyConsCode implements IntList {

  /* The only instance of Empty */
  static Empty ONLY = new Empty(); 

  /* Constructor */
  private Empty() {} 

  /* IntList methods */
  public String toStringHelp() { return ""; }

  public String toString() { return "()"; }
}

class Cons extends EmptyConsCode implements IntList {
  
  /* fields */
  private int first;
  private IntList rest;

  /* constructor */
  Cons(int f, IntList r) {
    first = f;
    rest = r;
  }

  /* accessors */
 
  /** returns first element of non-empty list */
  int getFirst() { return first; };    

  /** returns all but the first element of non-empty list */
  IntList getRest() { return rest; }
 
  public String toString() {
    // no leading space before first
    return "(" + first + rest.toStringHelp() + ")";
  }
  public IntList empty() { return Empty.ONLY; }
  
  public IntList cons(int i) { return new Cons(i, this); }
  public String toStringHelp() {
    // leading space before each elt 
    return " " + first + rest.toStringHelp();  
  }
}