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
Listclass. E.g. an accessorOption<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();
sb.append("[");
if (this.size > 0) {
sb.append(this.head);
for (List<A> ptr = this.tail; ptr.size > 0; ptr = ptr.tail) {
sb.append(",");
sb.append(ptr.head);
}
}
sb.append("]");
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>>() {
@Override
public List<String> apply(String s) {
return new List<String>(s, s);
}
};
final List<String> strings = new List<String>("foo", "bar", "baz");
System.out.println(strings);
System.out.println(strings.bind(repeatEachElement));
// example: square each element
final Function<Integer, List<Integer>> square = new Function<Integer, List<Integer>>() {
@Override
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);
System.out.println(numbers);
System.out.println(numbers.bind(square));
// --------------- //
// 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>>() {
@Override
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>>() {
@Override
public List<String> apply(Integer i) {
return new List<>(i.toString());
}
};
final Function<Integer, List<String>> nested = new Function<Integer, List<String>>() {
@Override
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
