Monadic Immutable Linked List in the Least Functional Language Evar

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 extends Monad>> {
    public static I return(A x);
    public I bind(Function> 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 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 {
public B apply(A x);
}

class List {
private final A head;
private final List 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 plus(List that) {
if (this.size == 0) return that;
return new List(this.head, this.tail.plus(that));
}

// a convenience constructor that

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.

StackExchange Code Review Q#41811, answer score: 4