functions.java

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

interface Function<A, B> {
	B apply(A arg);

	static <T> Function<T, T> identity() {
		return x -> x;
	}
}

interface Function2<A, B, C> {
	C apply(A arg1, B arg2);
}

List.java

interface List<T> {
	Option<T> head();
	List<T> tail();
	int size();

	<A> A bind(Function<T, A> fn, Function2<A, A, A> combine);
	List<T> join(List<T> list);

	static List<T> unit() {
		return new List<T>() {
			Option<T> head() {
				return Option.unit();
			}

			List<T> tail() {
				return this;
			}

			int size() {
				return 0;
			}

			<A> A bind(Function<T, A> fn, Function2<A, A, A> combine) {
				return null;
			}

			List<T> join(List<T> list) {
				return list;
			}
		}
	}

	static List<T> cons(final T head, final List<T> tail) {
		return new List<T>() {
			T head() {
				return head;
			}

			List<T> tail() {
				return tail;
			}

			int size() {
				return 1 + tail.size();
			}

			<A> A bind(Function<T, A> fn, Function2<A, A, A> combine) {
				return combine.apply(fn.apply(head), tail.bind(fn, combine));
			}

			List<T> join(List<T> list) {
				return cons(head, tail.join(list));
			}
		}
	}

	static List<T> cons(final Option<T> option, final List<T> tail) {
		return option.map(x -> cons(x, tail))
						.orElse(unit());
	}

	<A> List<A> flatMap(Function<T, List<A>> fn) {
		return bind(fn, (a, b) -> a.join(b));
	}

	<A> List<A> map(Function<T, A> fn) {
		return head.map(fn).bind(x -> cons(x, tail.map(fn)))
						.orElse(unit());
	}

	List<T> filter(Function<T, Boolean> fn) {
		return head.bind(x -> cons(x, tail.filter(fn)))
						.orElse(unit());
	}
}

Option.java

interface Option<T> {
	<A> A bind(Function<T, A> fn);
	
	// gimme back to null-land
	T get();
	T orElse(Function0<T> fn);

	static Option<T> unit() {
		return new Option<T>() {
			T get() { throw new NullPointerException(); }
			T orElse(Function0<T> fn) { return fn.apply(); }

			<A> A bind(Function<T, A> fn) {
				return null;
			}
		};
	}

	static Option<T> unit(final T value) {
		Objects.requireNonNull(value);

		return new Option<T>() {
			T get() { return value; }
			T orElse(Function0<T> fn) { return value; }

			<A> Option<A> bind(Function<T, A> fn) {
				return fn.apply(value);
			}
		};
	}

	<A> Option<A> flatMap(Function<T, Option<A>> fn) {
		return bind(fn);
	}

	<A> Option<A> map(Function<T, A> fn) {
		return bind(x -> wrap(fn.apply(x)));
	}

	Option<T> filter(Function<T, Boolean> fn) {
		return bind(x -> fn.apply(x) ? this : unit());
	}
}