Skip to content

Instantly share code, notes, and snippets.

@samskivert
Created September 10, 2014 21:51
Show Gist options
  • Save samskivert/121e424be7d87d8fc4fd to your computer and use it in GitHub Desktop.
Save samskivert/121e424be7d87d8fc4fd to your computer and use it in GitHub Desktop.
List.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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment