## 2007-10-03

### Algebraic Data Types and Java Generics (II)

Update 2007-10-05: I've reworked the code to make it simpler. The insight I had is that, since Java is rank-1 polymorphic, there is no way I can meaningfully abstract over the particular monad being used; however, the monadic class itself is the monadic type constructor. Hence, the type parameters are somewhat simpler.

There are many definitions of monads on the web, many very formal but that don't provide much insight if you're not formally inclined; some very poetic and even somewhat evocative but not very accurate, morally speaking. For our purposes, a monad takes values of type A and "wraps" them in, or marks them as values of type `Monad<A>`. This wrapper is mostly opaque and inviolable, except for a number of operations that makes using monads less than hopeless:

• Given a value x of type A, `unit(x)` wraps it and turns it into a monadic value of type `Monad<A>`
• Given a function f that takes values of type A and returns values of type `Monad<B>`, `bind(f, x)` "pipes" a value x of type `Monad<A>` into f, and returns the corresponding value of type `Monad<B>`. In effect, `bind` "lifts" f from taking plain values to accepting monadic values, keeping everything wrapped in the same paper, so to speak.

The intent of this rather puzzling machinery is one of representing "special" operations on values by way of their encapsulation in "tainted" procedures that cannot be escaped. The specialness of these operations might reside on their interacting with the environment, or on having "extra" structure on which they depend (state, privilege certificates, etcetera).

These operations must satisfy a number of properties, called the monad laws, with which we won't be concerned here. A monad could have just a little bit of extra structure: if there is a monadic value, call it `zero`, that satisfies `bind(f, zero) = zero` for all functions f, the monad is said to be a monad with zero. This is analogous to regular multiplication of numbers. In this case, the monad usually has another operation that "adds" two monadic values into a third, such that adding any value to the zero leaves that value unchanged; this is the monadic addition, and the extended monad is called a monad with plus.

As I wrote in concluding Part I, the `Option` type gives rise naturally to a monad. This monad is usually conceptualized as the failure monad, which encapsulates computations that might fail to return a value.

Before we start, we need some type-theoretic definitions. We've seen the type-safe functional object:

```interface Function<X, Y> {
Y apply(X value);
}
```

A functor is a parametric type (think of it as a "container type") with an operation `map` that, given a function f that transforms objects, applies it "inside itself":

```interface Functor<X> {
<Y> Functor<Y> map(Function<X, Y> f);
}
```

Another detail to take into account is that functions are strange with respect to specialization and subtyping. The more specific the return type is, the more specific the function returning it; however, the more specific the function the less specific its argument must be. This is called contravariance, and our functional parameters must take it into account.

To our monads. First, we must define what shape they will have in Java. As a container of values of type X, it can be viewed as a functional. Also, any monad should, at the least, provide a `bind` (since `unit` is a kind of "static factory", it cannot be included in the interface signature):

```interface Monad<X> extends Functor<X> {
<Y> Monad<Y> bind(Function<? super X, ? extends Monad<Y>> f);
}
```

The type of `bind` is complicated by the fact that it must express the covariance-contravariance of its functional argument. A `MonadPlus` extends a `Monad` with zero with an operation `plus`:

```interface MonadPlus<X> extends Monad<X> {
}
```

(again, the `zero` is a static constructor, and cannot be included in the interface.) Now for casting an `Option` into a `Monad`ic shape (it will actually be a `MonadPlus`):

```abstract class Option<X> implements MonadPlus<X> {
```

The interface obligations for `MonadPlus` will be kept implicit; we will use the same trick as before to defer functionality to inner classes. The first case is that of the `Some` type constructor. It naturally subclasses `Option`:

```  public static class Some<X> extends Option<X> {
private final X value;
private Some(X value) { this.value = value; }
```

The `Functor` interface requires implementing `map`. Naturally, it transforms the value and wraps it in a new `Some`:

```    public <Y> Option<Y> map(Function<X, Y> f) {
return new Some<Y>(f.apply(this.value));
}
```

The `Monad` interface requires implementing `bind`. For a `Some(x)` option, it suffices to apply f to its value and return the result:

```    public <Y> Monad<Y> bind(Function<? super X, ? extends Monad<Y>> f) {
return f.apply(this.value);
}
```

To comply with `MonadPlus` interface, the `plus` operation must return the first argument that is not `zero`. Since `Some` is not the zero of the monad, it returns itself:

```    public MonadPlus<X> add(MonadPlus<X> _) {
return this;
}
}
```

The other constructor is `None`:

```  public static class None<X> extends Option<X> {
private None() { }
```

The `map` on it returns `None`, as tere is no value to supply to f:

```    public <Y> Option<Y> map(Function<X, Y> _) {
return new None<Y>();
}
```

Note: I could have returned `this` here, as there is conceptually just one value `None`. However, the type of `this` is parameterized by X while the result must be parameterized by Y. The alternative is to use an unchecked cast, `return (None<Y>) this;`. This is type-safe but uglier.

Ditto for `bind`:

```    public <Y> Monad<Y> bind(Function<? super X, ? extends Monad<Y>> _) {
return new None<Y>();
}
```

The `plus` returns its argument, as the left side is `this` of class `None`, which by definition is the `zero` of the monad:

```    public MonadPlus<X> add(MonadPlus<X> x) {
return x;
}
}
```

As before, we seal the `Option` class from extension:

```  private Option() { }
```

And let code create optional values using static constructors:

```  public static <X> Option<X> unit(X x) { return new Some<X>(x); }
public static <X> Option<X> zero(   ) { return new None<X>( ); }
}
```

This completes a type-safe implementation of the `Option` monad (equivalent to Haskell's `MaybeMonad`) in Java. We can test its usage:

```public class OptionTest {
public static void main(String[] args) {
Function<Integer, Option<Integer>> f = new Function<Integer, Option<Integer>>() {
public Option<Integer> apply(Integer x) {
System.out.println("n = "+x);
return Option.zero();
}
};
Function<Integer, Option<Integer>> g = new Function<Integer, Option<Integer>>() {
public Option<Integer> apply(Integer x) {
System.out.println("n = "+x);
return Option.unit(x + 10);
}
};
final Option<Integer> zero = Option.zero();
Note that we have to help Java's type checker by assigning `Option.zero()` to a variable of the right type.