Immutable Lists

ImmutableList.java

public abstract class ImmutableList<T> implements Iterable<T> {
    public abstract T head();

    public abstract ImmutableList<T> tail();

    public abstract boolean isEmpty();

    public ImmutableList<T> prepend(T element) {
        return new NonEmptyList<T>(element, this);
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private ImmutableList<T> list = ImmutableList.this;

            @Override
            public boolean hasNext() {
                return !list.isEmpty();
            }

            @Override
            public T next() {
                T element = list.head();
                list = list.tail();
                return element;
            }

            @Override
            public void remove() {
                // Java iterators must implement remove(), even though they
                // make no sense for immutable collections. Fortunately,
                // it is specified as an optional operation.
                throw new RuntimeException("Cannot remove from immutable list");
            }
        };
    }

    public static <T> ImmutableList<T> nil() {
        return EMPTY_LIST;
    }

    private static final EmptyList EMPTY_LIST = new EmptyList();

    private static class EmptyList extends ImmutableList {
        @Override
        public Object head() {
            throw new NoSuchElementException("head() called on empty list");
        }

        @Override
        public ImmutableList tail() {
            throw new NoSuchElementException("tail() called on empty list");
        }

        @Override
        public boolean isEmpty() {
            return true;
        }
    }

    private static class NonEmptyList<T> extends ImmutableList<T> {
        private final T element;
        private final ImmutableList<T> tail;

        private NonEmptyList(final T element, final ImmutableList<T> tail) {
            this.element = element;
            this.tail = tail;
        }

        @Override
        public T head() {
            return element;
        }

        @Override
        public ImmutableList<T> tail() {
            return tail;
        }

        @Override
        public boolean isEmpty() {
            return false;
        }
    }
}

ImmutableList_reverse_tailrec.java

public abstract class ImmutableList<T> implements Iterable<T> {
    /*  ... previous method and subclass definitions ... */

    public ImmutableList<T> reverse() {
        return reverseHelper(this, ImmutableList.<T>nil());
    }

    // This tail-recursive function "pours" values off the input stack
    // onto the output stack. Unfortunately, it will also overflow the stack
    // for a large input list.
    private static <T> ImmutableList<T> reverseHelper(ImmutableList<T> input,
                                                      ImmutableList<T> output) {
        if (input == nil()) {
            return output;
        }
        return reverseHelper(input.tail(), output.prepend(input.head()));
    }
}

ImmutableList_reverse_while.java

public abstract class ImmutableList<T> implements Iterable<T> {
    /*  ... previous method and subclass definitions ... */

    public ImmutableList<T> reverse() {
        ImmutableList<T> input = this;
        ImmutableList<T> output = nil();
        while (input != nil()) {
            output = output.prepend(input.head());
            input = input.tail();
        }
        return output;
    }
}

ImmutableList_size.java

public abstract class ImmutableList<T> implements Iterable<T> {
    /*  ... previous method and static class definitions ... */

    public final int size() {
        if (isEmpty()) {
            return 0;
        }
        return 1 + tail().size();
    }
}

ImmutableList_size_final.java

public abstract class ImmutableList<T> implements Iterable<T> {
    /*  ... previous method and static class definitions ... */

    public final int size() {
        ImmutableList<T> input = this;
        int size = 0;
        while (!input.isEmpty()) {
            size++;
            input = input.tail();
        }
        return size;
    }
}

ImmutableList_size_tailrec.java

public abstract class ImmutableList<T> implements Iterable<T> {
    /*  ... previous method and static class definitions ... */

    public final int size() {
        return sizeHelper(this, 0);
    }

    // This method is tail-recursive. When it calls itself, it is the last
    // operation before returning.
    // Unfortunately, it still overflows the stack in Java.
    private static <T> int sizeHelper(ImmutableList<T> input, int output) {
        if (input.isEmpty()) {
            return output;
        }
        return sizeHelper(input.tail(), output + 1);
    }
}

ImmutableList_size_tailrec_optimized.java

public abstract class ImmutableList<T> implements Iterable<T> {
    /*  ... previous method and static class definitions ... */
    public final int size() {
        return sizeHelper(this, 0);
    }

    // This method compiles to roughly the same bytecode as the tail-recursive
    // version of sizeHelper would, if the Java compiler supported tail-call
    // optimization. (The while(true) basically gives us a "goto" back to the
    // start of the method.)
    private static <T> int sizeHelper(ImmutableList<T> input, int output) {
        while (true) {
            if (input.isEmpty()) {
                return output;
            }
            output = output + 1;
            input = input.tail();
        }
    }
}

ImmutableList_varargs.java

public abstract class ImmutableList<T> implements Iterable<T> {
    /*  ... previous method and static class definitions ... */

    public static <T> ImmutableList<T> list(T... elements) {
        ImmutableList<T> output = nil();
        for (int i = elements.length - 1; i >= 0 ; i--) {
            output = output.prepend(elements[i]);
        }
        return output;
    }
}

ImmutableListTest_iteration.java

import org.junit.Test;

import static collections.ImmutableList.list;
import static org.junit.Assert.assertEquals;

public class ImmutableListTest {

    @Test
    public void testListIteration() {
        ImmutableList<Integer> list = list(1, 2, 3);
        int i = 1;
        for (Integer l : list) {
            assertEquals(i++, l.intValue());
        }
    }
}

ImmutableListTest_size.java

/* ... previous imports ... */

public class ImmutableListTest {

    /* ... previous test definitions ... */

    // This tests the size() method using a relatively large
    // list of 100k Bytes. A recursive implementation of 
    // size() won't be able to handle that many recursive
    // calls on the stack.
    @Test
    public void testSize() throws Exception {
        int size = 100000;
        Byte[] bytes = new Byte[size];
        for (int i = 0; i < size; i++) {
            bytes[i] = (byte) (i % 256);
        }
        ImmutableList<Byte> byteList = list(bytes);
        assertEquals(size, byteList.size());
    }
}