List.java

gistfile1.java

//
// Scaled - a scalable editor extensible via JVM languages
// http://github.com/scaled/scaled/blob/master/LICENSE

package scaled;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * A simple functional list class, built from cons cells as God and John McCarthy intended.
 */
public abstract class List<E> implements Iterable<E> {

  /** Returns the empty list. */
  public static <A> List<A> nil () {
    @SuppressWarnings("unchecked") List<A> nil = (List<A>)NIL;
    return nil;
  }

  /** Creates a list that contains {@code value}. */
  public static <A> List<A> apply (A value) {
    return cons(value, nil());
  }

  /** Creates a list that contains {@code [a, b]}. */
  public static <A> List<A> apply (A a, A b) {
    return cons(a, cons(b, nil()));
  }

  /** Creates a list that contains {@code [a, b, c]}. */
  public static <A> List<A> apply (A a, A b, A c) {
    return cons(a, cons(b, cons(c, nil())));
  }

  /** Creates a list that contains {@code values}. */
  @SafeVarargs public static <A> List<A> apply (A... values) {
    List<A> list = nil();
    for (int ii = values.length-1; ii >= 0; ii -= 1) list = list.cons(values[ii]);
    return list;
  }

  /** Returns a new list with {@code elem} consed onto its head. */
  public static <B> List<B> cons (B head, List<? extends B> tail) {
    @SuppressWarnings("unchecked") List<B> casted = (List<B>)tail;
    return new Cons<B>(head, casted);
  }

  // ----- List API ---------------------------------------------

  /** Returns the size of this list. NOTE: this is an O(n) operation. */
  public int size () {
    int size = 0;
    for (List<E> list = this, nil = nil(); list != nil; list = list.tail()) {
      size += 1;
    }
    return size;
  }

  /**
   * Returns the head of this list.
   * @throws NoSuchElementException if called on the {@code nil} list.
   */
  public abstract E head ();

  /**
   * Returns the tail of this list.
   * @throws NoSuchElementException if called on the {@code nil} list.
   */
  public abstract List<E> tail ();

  /**
   * Returns a new list with {@code elem} consed onto its head. Note: due to limitations of Java's
   * type system, this method is invariant. Use the static {@code List.cons} if you need the proper
   * contravariance.
   */
  public List<E> cons (E elem) {
    return new Cons<E>(elem, this);
  }

  /**
   * Returns an iterator over this list. Note that {@link Iterator#remove} is not supported.
   */
  public Iterator<E> iterator () {
    return new Iterator<E>() {
      private List<E> cur;
      @Override public boolean hasNext() {
        return cur != nil();
      }
      @Override public E next () {
        List<E> cur = this.cur;
        this.cur = cur.tail();
        return cur.head();
      }
      @Override public void remove () {
        throw new UnsupportedOperationException();
      }
    };
  }

  // ----- List impl ---------------------------------------------

  private static final Nil NIL = new Nil();

  private static class Nil extends List<Object> {
    @Override public Object head () { throw new NoSuchElementException("nil.head()"); }
    @Override public List<Object> tail () { throw new NoSuchElementException("nil.tail()"); }
  };

  private static class Cons<E> extends List<E> {
    @Override public E head () { return head; }
    @Override public List<E> tail () { return tail; }

    private Cons (E head, List<E> tail) {
      if (tail == null) throw new IllegalArgumentException("List tail must not be null.");
      this.head = head;
      this.tail = tail;
    }

    private final E head;
    private final List<E> tail;
  }
}