JDK1.8, Project Lambda, immutable single linked list

List.java

import java.util.Comparator;
import java.util.Iterator;
import java.util.functions.*;

interface Function0<R> {
  R apply();
}

interface Function1<P1, R> {
  R apply(P1 p1);
}

interface Function2<P1, P2, R> {
  R apply(P1 p1, P2 p2);
}

/**
 * A homogeneous immutable single linked list. This list implementation is fast
 * by prepending elements to it, removing its head or iterating through the
 * elements. It is not efficient to search for or to change single elements.
 * <p>
 * ATTENTION: This code compiles only with JDK1.8 and project lambda which can
 * be found at http://jdk8.java.net/lambda/ and is not production ready.
 *
 * @author Antoras
 * @version 0.1
 * @since JDK1.8, Mar 6, 2012
 * @param <A>
 *        The element type of the list.
 */
public abstract class List<A> implements Iterable<A> {

  /**
   * Creates a new list with the given elements.
   *
   * @param <A>
   *        the type of the elements
   */
  @SuppressWarnings("unchecked")
  public static <A> List<A> of(final A... as) {
    List<A> xs = nil();
    for (final A a : as) {
      xs = xs.cons(a);
    }
    return xs.reverse();
  }

  /**
   * Transforms a String to a list.
   */
  public static List<Character> from(final String str) {
    List<Character> xs = nil();
    for (final char c : str.toCharArray()) {
      xs = xs.cons(c);
    }
    return xs.reverse();
  }

  /**
   * Creates a list which holds the values in a given range.
   */
  public static List<Integer> range(final int from, final int to) {
    List<Integer> xs = nil();
    for (int i = from; i <= to; ++i) {
      xs = xs.cons(i);
    }
    return xs.reverse();
  }

  /**
   * The empty list.
   */
  @SuppressWarnings("unchecked")
  public static <B> List<B> nil() {
    return NIL;
  }

  /**
   * The head of a list is the first element.
   *
   * @return the first element.
   */
  public abstract A head();

  /**
   * The tail of a list is the list itself without its first element.
   */
  public abstract List<A> tail();

  /**
   * The init of a list is a list which contains all elements of the original
   * list without its last element.
   */
  public abstract List<A> init();

  /**
   * The last element of the list
   */
  public abstract A last();

  /**
   * Checks whether a list is empty or not.
   *
   * @return always true if the list is equal to {@link List#nil()}, false
   *         otherwise.
   */
  public abstract boolean isEmpty();

  /**
   * Returns the size of the list. This is the number of elements without the
   * NIL type.
   */
  public int size() {
    int sum = 0;
    List<A> xs = this;
    while (!xs.isEmpty()) {
      sum += 1;
      xs = xs.tail();
    }
    return sum;
  }

  /**
   * Prepends an element to the list.
   *
   * @param a
   *        the element to prepend
   * @return the prepended element whose tail is the old list.
   */
  public List<A> cons(final A a) {
    return new Cons<A>(a, this);
  }

  /**
   * Prepends another list to this list.
   */
  public List<A> consAll(final List<A> xs) {
    if (isEmpty()) {
      return xs;
    }
    if (xs.isEmpty()) {
      return this;
    }
    List<A> ys = this;
    for (final A a : xs.reverse()) {
      ys = ys.cons(a);
    }
    return ys;
  }

  /**
   * Appends another list to this list. Appending elements to a single linked
   * list is not efficient, therefore prepend them.
   */
  public List<A> addAll(final List<A> xs) {
    if (isEmpty()) {
      return xs;
    }
    return xs.consAll(this);
  }

  /**
   * Returns the element at the given index. The indext starts by 0.
   */
  public A get(final int index) {
    if (isEmpty() || index < 0 || index >= size()) {
      throw new IndexOutOfBoundsException(String.valueOf(index));
    }
    List<A> xs = this;
    int i = 0;
    while (i != index) {
      ++i;
      xs = xs.tail();
    }
    return xs.head();
  }

  /**
   * Takes the first n elements and returns them.
   */
  public List<A> take(final int n) {
    if (n <= 0) {
      return nil();
    }
    if (n >= size()) {
      return this;
    }
    List<A> xs = this;
    int i = 0;
    List<A> ys = nil();
    while (i != n) {
      ++i;
      ys = ys.cons(xs.head());
      xs = xs.tail();
    }
    return ys.reverse();
  }

  /**
   * Drops the first n elements and returns the remaining elements.
   */
  public List<A> drop(final int n) {
    if (n >= size()) {
      return nil();
    }
    List<A> xs = this;
    int i = n;
    while (i > 0) {
      --i;
      xs = xs.tail();
    }
    return xs;
  }

  /**
   * Iterates through the elements and execute a function to all of them. The
   * function to execute expects only the element and has no return value.
   *
   * @param f
   *        the function to execute
   */
  public void forEach(final Block<? super A> f) {
    List<A> xs = this;
    while (!xs.isEmpty()) {
      f.apply(xs.head());
      xs = xs.tail();
    }
  }

  /**
   * Takes a function which converts each value of the list to another one.
   *
   * @param f
   *        the function to convert the elements
   * @return a new list with the new values
   */
  public <B> List<B> map(final Mapper<? super A, ? extends B> f) {
    return foldLeft(List.<B>nil(), (xs, x) -> xs.cons(f.map(x))).reverse();
  }

  /**
   * Takes a function which checks if an element has a specific predicate. Is
   * this the case the element is added to the list, which will be returned at
   * the end.
   *
   * @param f
   *        the function to check the predicate
   * @return a new list which contains only the elements with the predicate
   */
  public List<A> filter(final Predicate<? super A> f) {
    return foldLeft(List.<A>nil(), (xs, x) -> f.eval(x) ? xs.cons(x) : xs).reverse();
  }

  /**
   * Returns a list which contains the elements of the lists returned by the
   * function.
   */
  public <B> List<B> flatMap2(final Mapper<? super A, ? extends List<B>> f) {
    final List<List<B>> xs = map(f);
    final List<B> ys = xs.tail().reduceLeft((a, b) -> a.consAll(b.reverse()));
    return xs.head().reverse().consAll(ys).reverse();
  }

  /**
   * Checks if the list contains a given element.
   */
  public boolean contains(final A elem) {
    for (final A a : this) {
      if (a.equals(elem)) {
        return true;
      }
    }
    return false;
  }

  /**
   * Checks if the list contains an element which has a specific predicate. Is
   * such an element found it is returned wrapped in an Option. Otherwise an empty Option is returned.
   * <p>
   * In idiomatic functional programming a data type like Option is
   * returned instead of returned plain old null due to type safety.
   */
  public Option<A> find(final Predicate<A> f) {
    for (final A a : this) {
      if (f.eval(a)) {
        return Option.some(a);
      }
    }
    return Option.none();
  }

  /**
   * Checks if the list contains an element which has a specific predicate.
   * Returns true if such an element is found, false otherwise.
   */
  public boolean exists(final Predicate<A> f) {
    return find(f) != Option.none();
  }

  /**
   * Reverses the list.
   */
  public List<A> reverse() {
    return foldLeft(List.<A>nil(), (xs, x) -> xs.cons(x));
  }

  /**
   * Folds from left to right through the list.
   */
  public <B> B foldLeft(final B init, final Function2<B, A, B> f) {
    B ret = init;
    List<A> xs = this;
    while (!xs.isEmpty()) {
      ret = f.apply(ret, xs.head());
      xs = xs.tail();
    }
    return ret;
  }

  /**
   * Works like foldLeft but its start value is the first element of the list.
   */
  public A reduceLeft(final Function2<A, A, A> f) {
    if (isEmpty()) {
      throw new UnsupportedOperationException("nil.reduceLeft");
    }
    return tail().foldLeft(head(), f);
  }

  public Iterator<A> iterator() {
    return new Iterator<A>() {

      List<A> xs = List.this;

      public boolean hasNext() {
        return !xs.isEmpty();
      }

      public A next() {
        final A x = xs.head();
        xs = xs.tail();
        return x;
      }

      public void remove() {
        // TODO I can't take it anymore ;)
        throw new UnsupportedOperationException("List.iterator.remove");
      }
    };
  }

  /**
   * Unpacks all elements of sublists and add the to a single one.
   */
  public List<Object> flatten() {
    if (isEmpty()) {
      return nil();
    }
    if (head() instanceof List<?>) {
      return ((List<?>) head()).flatten().addAll(tail().flatten());
    }
    return tail().flatten().cons(head());
  }

  public String mkString() {
    return mkString("", "", "");
  }

  public String mkString(final String start, final String sep, final String end) {
    final StringBuilder sb = new StringBuilder();
    sb.append(start);
    if (!isEmpty()) {
      sb.append(head());

      for (final A x : this.tail()) {
        sb.append(sep);
        sb.append(x);
      }
    }

    sb.append(end);
    return sb.toString();
  }

  public List<A> qsort(final Comparator<A> comp) {
    if (isEmpty()) {
      return nil();
    }
    final List<A> xs = tail().filter(a -> comp.compare(a, head()) < 0);
    final List<A> ys = tail().filter(a -> comp.compare(a, head()) >= 0);
    return ys.qsort(comp).cons(head()).consAll(xs.qsort(comp));
  }

  @Override
  public int hashCode() {
    return foldLeft(37, (sum, x) -> sum * 7 + x.hashCode());
  }

  @Override
  public boolean equals(final Object obj) {
    if (obj == this) {
      return true;
    }
    if (obj instanceof List) {
      List<?> xs = (List<?>) obj;

      if (size() != xs.size()) {
        return false;
      }

      for (final Object x : this) {
        if (!x.equals(xs.head())) {
          return false;
        }
        xs = xs.tail();
      }
      return true;
    }
    return false;
  }

  @Override
  public String toString() {
    return mkString("List(", ", ", ")");
  }

  /**
   * End of the list. Should not used directly because of missing type
   * inference. Use {@link List#nil()} instead.
   */
  @SuppressWarnings("rawtypes")
  public static final List NIL = new List<Object>() {

    @Override
    public Object head() {
      throw new UnsupportedOperationException("nil head");
    }

    @Override
    public List<Object> tail() {
      throw new UnsupportedOperationException("nil tail");
    }

    @Override
    public List<Object> init() {
      throw new UnsupportedOperationException("nil init");
    }

    @Override
    public Object last() {
      throw new UnsupportedOperationException("nil last");
    }

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

/**
 * Element of the list. Don't refer to this class directly. Instead access the
 * elements of a list by using its methods.
 *
 * @version 0.1
 * @since JDK1.6, Mar 6, 2012
 * @param <A>
 *        The element type of the list.
 */
final class Cons<A> extends List<A> {

  private final A head;
  private final List<A> tail;

  public Cons(final A head, final List<A> tail) {
    this.head = head;
    this.tail = tail;
  }

  @Override
  public A head() {
    return head;
  }

  @Override
  public List<A> tail() {
    return tail;
  }

  @Override
  public List<A> init() {
    return take(size() - 1);
  }

  @Override
  public A last() {
    return drop(size() - 1).head();
  }

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