Pattern matching examples

ImmutableList.java

public abstract class ImmutableList<T> {
  
  /*
   * Operations
   */
  public abstract T head();
  public abstract ImmutableList<T> tail();
  public abstract <R> ImmutableList<R> map(Function<T, R> f);
  public final ImmutableList<T> prepend(T elem) {
    return new NonEmptyList<>(elem, this);
  }

  /*
   * Factory method to get the EmptyList
   */
  public static <R> EmptyList<R> empty() {
    //noinspection unchecked
    return EMPTY;
  }
  private static final EmptyList EMPTY = new EmptyList();  

  /*
   * Implementations
   */
  private static class EmptyList<T> extends ImmutableList<T> {
    @Override
    public T head() {
      throw new IndexOutOfBoundsException("head() of empty list");
    }

    @Override
    public ImmutableList<T> tail() {
      throw new IndexOutOfBoundsException("tail() of empty list");
    }

    @Override
    public <R> ImmutableList<R> map(Function<T,R> f) {
      return empty();
    }
  }

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

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

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

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

    @Override
    public <R> ImmutableList<R> map(final Function<T, R> f) {
      return tail().map(f).prepend(f.apply(head()));
    }
  }
}

ImmutableList2.java

public class ImmutableList2<T> {
  /*
   * Internal types -- should never need to change
   */
  private static class EmptyList extends ImmutableList2 {
  }

  private static final EmptyList EMPTY = new EmptyList();

  private static class NonEmptyList<T> extends ImmutableList2<T> {
    private final T head;
    private final ImmutableList2<T> tail;

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

    private T head() {
      return head;
    }

    private ImmutableList2<T> tail() {
      return tail;
    }
  }

  /*
   * Operations on above types
   */

  public static <R> ImmutableList2<R> empty() {
    //noinspection unchecked
    return EMPTY;
  }

  public static <T> ImmutableList2<T> prepend(T elem,
                                              ImmutableList2<T> xs) {
    return new NonEmptyList<>(elem, xs);
  }

  public static <T> T head(ImmutableList2<T> xs) {
    if (Objects.equals(xs, EMPTY)) {
      throw new IndexOutOfBoundsException("head() of empty list");
    }
    if (xs instanceof NonEmptyList) {
      return ((NonEmptyList<T>) xs).head();
    }
    throw new RuntimeException("Match error for " + xs);
  }

  public static <T> ImmutableList2<T> tail(ImmutableList2<T> xs) {
    if (Objects.equals(xs, EMPTY)) {
      throw new IndexOutOfBoundsException("tail() of empty list");
    }
    if (xs instanceof NonEmptyList) {
      return ((NonEmptyList<T>) xs).tail();
    }
    throw new RuntimeException("Match error for " + xs);
  }

  public static <R, T> ImmutableList2<R> map(Function<T, R> f,
                                             ImmutableList2<T> xs) {
    if (Objects.equals(xs, EMPTY)) {
      return empty();
    }
    if (xs instanceof NonEmptyList) {
      NonEmptyList<T> xs2 = (NonEmptyList<T>) xs;
      return prepend(f.apply(xs2.head()), map(f, xs2.tail()));
    }
    throw new RuntimeException("Match error for " + xs);
  }

}

MyImmutableList.scala

sealed trait MyImmutableList[+T]
case object EmptyList extends MyImmutableList[Nothing]
case class NonEmptyList[T](head : T, tail: MyImmutableList[T]) extends MyImmutableList[T]

object MyImmutableList {
  def empty[T] = EmptyList

  def prepend[T](elem : T, xs : MyImmutableList[T]) =
    NonEmptyList(elem, xs)

  def head[T](xs : MyImmutableList[T]) = xs match {
    case EmptyList =>
      throw new IndexOutOfBoundsException("head() of empty list")
    case NonEmptyList(h,_) => h
  }

  def tail[T](xs : MyImmutableList[T]) = xs match {
    case EmptyList =>
      throw new IndexOutOfBoundsException("tail() of empty list")
    case NonEmptyList(_,t) => t
  }

  def map[T, R](f : (T => R), xs : MyImmutableList[T]) : MyImmutableList[R] = xs match {
    case EmptyList => EmptyList
    case NonEmptyList(h,t) =>
      prepend(f(h), map(f, t))
  }
}