hkt.txt

Higher-kinded types in Java
===========================

If we consider that types classify values, then kinds classify types. 
To use Haskell notation, simple java types are of kind * - the kind of types of values. 
Generic types (e.g. List) are of kind * -> * - this is essentially a type-level 
function - pass a type parameter A to the List type constructor and you get a List<A>.

Higher-kinded types are (basically) of kind (* -> *) -> *. 
Prime examples are Functor, Applicative and Monad.

A Functor, for example requires a type argument, that itself has a type argument. 
i.e. interface Functor<T<A>>, where a is kind * and T is kind * -> *. i.e. the type 
parameter itself is a parameterised type. So, I have to pass a parameterised type 
(e.g. List<A>) as the type argument.

The Functor interface has a single function:
<B> T<B> map(F<A, B> f)
(where F<A, B> is a first-class function)

Mapping over lists is common, as is mapping over Optionals, Eithers and any type 
with a type parameter. This idea of "mapping" generalises to a Functor and a set 
of functions can be implemented based on this abstraction. Applicative inherits 
from Functor, and Monad inherits from Applicative - at each level the interfaces 
add more requirements and have fewer instances, but give rise to more operations.

Notable examples of languages that include higher-kinded types as type-system feature 
are Scala, Haskell, PureScript, Idris and (soon) Ceylon.

Below is a code example of mapping over a simple immutable cell type.

package hk;

interface F<A, B> {
  B apply(final A a);
}

/** Functor interface - not currently expressible in Java */
public interface Functor<T<A>> {        // current Java has a compile error on this line
  public <B> T<B> map(final F<A, B> f);
}

/** Just a very simple immutable cell - a collection that holds one object */
class Cell<A> implements Functor<Cell<A>> {

  private final A a;

  public Cell(final A a) {
    this.a = a;
  }

  public A get() {
    return a;
  }

  @Override
  public <B> Cell<B> map(final F<A, B> f) {
    return new Cell<B>(f.apply(a));
  }
}