Basics

Basics

The Problem

The problem is that Java doesn't support higher order type polymorphism ("higher kinded types", as Scala calls it). E.g. it's easy to write a functor for a given generic class like List:

public class ListFunctor {
  public <A,B> List<B> map(Function<A,B> fn, List<A> source) {
     ...
  }
}

public class OptionalFunctor {
  public <A,B> Optional<B> map(Function<A,B> fn, Optional<A> source) {
     ...
  }
}

As you can see, a functor can "translate" the values inside a "container" using a function. Functors are not only a useful, but are also a very common structure, so we would like to abstract over this concept. But in Java you can't. We would need something like:

public class Functor<X<?>> {
  public <A,B> X<B> map(Function<A,B> fn, X<A> source) {
     ...
  }
}

This is not possible. We can't say "regardless what X is, if you put an X<A> in map, you will get an X<B> back". The abstraction over A and B is not enough, we need to abstract over the container, in order to write functors for lists, sets, maps, functions etc.

The Solution

The only way I found to simulate higher order type polymorphism in Java is to use the abstraction we already have, that is the abstraction of the the type parameters. To do this we need to separate the "container type" from it's value type, and then making it a type parameter itself. So instead of List<String> we have something like Something<List<?>, String>. Now the container is independent from it's value, and we can abstract over it.

In order to make things more readable and to draw the attention to List instead of Something, I used __ (2 underscores) as name for the Something. Further I found it ugly to use List<?> as type parameter, so I use a static inner class List.µ which serves as type parameter instead of List. I call this inner µ class the "witness" of the outer class. Classes like List<A> extend their version of the higher order base class, e.g. __<List.µ,A>. An annotation processor (which is part of the derive4j project) generates a class Hkt, which contains all the function like public static <A> List<A> asList(_<List.µ,A> value) needed to convert back to the original type.

The remaining problem is security: How can Hkt.<A>asList(value) know for sure that value is internally really a list? There are ways to make this more safe (at least at runtime), but in the end you can't guard against casts, raw types or reflection. I found that making __ a class is quite restricting, so I lowered the security standards and made it an interface. That means if you write a class like class Foo<A> extends __<List.µ, A>, and use it with highJ's type-classes, it will very likely blow up with a ClassCastException.

As long as you don't want to implement a type constructor yourself, you don't need to know such details. The important thing is that we can finally write a general functor interface, and implement it for arbitrary type constructors:

public interface Functor<X> {
  public <A,B> __<X,B> map(Function<A,B> fn, __<X,A> source);
}

public class ListFunctor implements Functor<List.µ> {
  public <A,B> __<List.µ, B> map(Function<A,B> fn, __<List.µ, A> source) {
     ...
  }
}

Everything else in highJ follows this scheme.

For classes with two type arguments there is a __2 wrapper interface as "curried" type of __, so you can write functor instances for types like Either<A,B> as well. If you want, you can go fancy with the classes ___3 and ____4.

I know the short names like __ and µ are confusing at first, but the type signatures are already rather long and I didn't want to make them even longer. After a short time these symbols really help to glance over some code and to "see" what is important and what is just "library noise" which can usually be ignored.