I've written a List monad as an example for a related question. This is a rather frustrating experience as I wanted to use Java, which (as of Java 7) still lacks lambda expressions and lacks higher-order type parameters, which is one reason why this

interface Monad<A, I<A> extends Monad<A, I<A>>> {
    public static I<A> return(A x);
    public I<B> bind(Function<A, I<B>> f);

is impossible. Also, return-type polymorphism would be great. But I digress.

I am looking for a review of the following:

  • general style.
  • general correctness, considering that I wouldn't claim to actually understand monads.
  • ways to increase the type safety and generality, considering that an interface as above is impossible as of my knowledge.
  • ways to reduce verbosity without sacrificing conceptual elegance.

I am not looking for a review of

  • … the lack of JavaDoc-comments, as this is educational code.
  • … ease of use of the List class. E.g. an accessor Option<A> get(int i) would be contrary to the purpose of this code as a monad showcase.

Here is the implementation itself:

import java.lang.String;
import java.lang.StringBuilder;
import java.lang.Integer;
import java.lang.System;

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

class List<A> {
    private final A         head;
    private final List<A>   tail;
    private final int       size;

    // unit :: A -> M[A]
    // public List(A x) -- implied by "new List<>(A...)"

    // "List" happens to be *additive*, so we also offer a "zero" instance 
    // and a "plus" operation

    // "zero", a neutral element for the "plus" operation
    // public List()  -- implied by "new List<>(A...)"

    // "plus" concatenates two Lists
    //     plus :: (M[A], M[A]) → M[A]
    // important properties regarding the zero:
    //     zero.plus(x) == x
    //     x.plus(zero) == x
    public List<A> plus(List<A> that) {
        if (this.size == 0) return that;
        return new List<A>(this.head, this.tail.plus(that));

    // a convenience constructor that hides excessive "plus"sing
    public List(A... xs) {
        // technically, we have to do something like:
        //     List<A> result = new List<>();
        //     for (A x : xs)
        //        result = result.plus(new List<>(x));
        //     this = result
        // let's take the equivalent shortcut:

        if (xs.length == 0) {
            this.head   = null;
            this.tail   = null;
            this.size   = 0;
        else {
            List<A> result = new List<A>();
            for (int i = xs.length - 1; i > 0; i--) {
                result = new List<A>(xs[i], result);
            this.head   = xs[0];
            this.tail   = result;
            this.size   = result.size + 1;

    // an internal constructor to create the linked lists
    private List(A x, List<A> xs) {
        this.head   = x;
        this.tail   = xs;
        this.size   = xs.size + 1;

    // "bind"
    //     bind :: (M[A], A → M[B]) → M[B]
    // can be implemented in terms of our "plus"
    public <B> List<B> bind(Function<A, List<B>> f) {
        if (this.size == 0) return new List<B>();
        List<B> partialResult = this.tail.bind(f);
        return f.apply(this.head).plus(partialResult);

    // how about a nice "toString"?
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (this.size > 0) {
           for (List<A> ptr = this.tail; ptr.size > 0; ptr = ptr.tail) {
        return sb.toString();

And here is some example usage:

public class Main {
    public static void main (String[] args)
        // example: repeat each element
        final Function<String, List<String>> repeatEachElement = new Function<String, List<String>>() {
            public List<String> apply(String s) {
                return new List<String>(s, s);
        final List<String> strings = new List<String>("foo", "bar", "baz");

        // example: square each element
        final Function<Integer, List<Integer>> square = new Function<Integer, List<Integer>>() {
            public List<Integer> apply(Integer i) {
                return new List<Integer>(i * i);
        final List<Integer> numbers = new List<Integer>(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

        // --------------- //
        // The Monad Laws: //
        // --------------- //

        // note: these aren't _proofs_ of correctnes,
        // just some examples showing that they're probably correct.

        // 1. "(unit x) >>= f ≡  f x" //
        assert new List<Integer>(42).bind(square).toString() == square.apply(42).toString();

        // 2. "m >>= unit ≡  m" //
        final Function<Integer, List<Integer>> unit = new Function<Integer, List<Integer>>() {
            public List<Integer> apply(Integer i) {
                return new List<>(i);
        assert numbers.bind(unit).toString() == numbers.toString();

        // 3. "(m >>= f) >>= g   ≡   m >>= ( \x -> (f x >>= g) )" //
        // m = numbers
        // f = square
        // g = stringify
        final Function<Integer, List<String>> stringify = new Function<Integer, List<String>>() {
            public List<String> apply(Integer i) {
                return new List<>(i.toString());
        final Function<Integer, List<String>> nested = new Function<Integer, List<String>>() {
            public List<String> apply(Integer i) {
                return square.apply(i).bind(stringify);
        assert numbers.bind(square).bind(stringify).toString()
            == numbers.bind(nested).toString();

See it in action here: http://ideone.com/S3r7v6


1 Answer 1


This is pretty decent code. A few things seem noteworthy:

  • The spacing is inconsistent. This could have happened if size was a boolean isEmpty in a previous incarnation…

  • There are a lot more opportunities to declare variables to be final than were used.

  • The documentation inside the methods is a bit sparse. For example, it would be helpful to explicitly point out that for (int i = xs.length - 1; i > 0; i--) goes through the array backwards, but will stop before the first element.

  • The toString is missing an @Override.

  • It might be cheaper to do an sb.append(',') than sb.append(",") (char vs. String).

  • Testing with assert is a horrible idea, but admittedly good enough for educational code.

  • In March 2014, Java 8 will be released, and the horribly verbose Function definitions can be shortened to lambdas. Yay!

  • Actually, writing an Option implementation (aka. Maybe) alongside of the List would be fairly useful – it too is an additive monad, even simpler in its implementation, and would help to highlight which part of the code is for the monads, and which is for the linked list.

  • In the test for the third monad law, f (here: square) has type Integer → Integer. Thus we only test this with two different types, although in general we should be able to test three different types. A sqroot :: Integer -> Double might have had more illustrative value. Also, stringify actually has the type Object → String.

  • \$\begingroup\$ I mostly agree. But could you elaborate why using assertions is "a horrible idea"? I disagree and like the clear intent that is delivered by using assert. Of course -ea has to be active... \$\endgroup\$ Commented Feb 20, 2014 at 16:57
  • 1
    \$\begingroup\$ @CarstenHoffmann assert is meant to check invariants and contracts, e.g. that the argument to a method isn't null. If an assertion fails, an AssertionError is thrown which isn't meant to be caught. Thus, an assertion-based test suite will have at most one failing test. A framework like JUnit has a more nuanced approach. It provides abstractions over common tests, and can output a summary, making a statement like “we now pass 97% of the test suite” possible. It's also easier to explain why a test failed when using such a framework. \$\endgroup\$
    – amon
    Commented Feb 20, 2014 at 17:15
  • \$\begingroup\$ Totally get your point. Thanks for clearing that up. I somehow understood your objection against assert as a general statement. \$\endgroup\$ Commented Feb 20, 2014 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.