Structural Pattern Matching in Java

One of the great features of modern programming languages is structural pattern matching on algebraic data types. Once you’ve used this feature, you don’t ever want to program without it. You will find this in languages like Haskell and Scala.

In Scala, algebraic types are provided by case classes. For example:

sealed trait Tree
case object Empty extends Tree
case class Leaf(n: Int) extends Tree
case class Node(l: Tree, r: Tree) extends Tree

To define operations over this algebraic data type, we use pattern matching on its structure:

def depth(t: Tree): Int = t match {
  case Empty => 0
  case Leaf(n) => 1
  case Node(l, r) => 1 + max(depth(l), depth(r))
}

When I go back to a programming language like, say, Java, I find myself wanting this feature. Unfortunately, algebraic data types aren’t provided in Java. However, a great many hacks have been invented over the years to emulate it, knowingly or not.

The Ugly: Interpreter and Visitor

What I have used most throughout my career to emulate pattern matching in languages that lack it are a couple of hoary old hacks. These venerable and well respected practises are a pair of design patterns from the GoF book: Interpreter and Visitor.

The Interpreter pattern really does describe an algebraic structure, and it provides a method of reducing (interpreting) the structure. However, there are a couple of problems with it. The interpretation is coupled to the structure, with a “context” passed from term to term, and each term must know how to mutate the context appropriately. That’s minus one point for tight coupling, and minus one for relying on mutation.

The Visitor pattern addresses the former of these concerns. Given an algebraic structure, we can define an interface with one “visit” method per type of term, and have each term accept a visitor object that implements this interface, passing it along to the subterms. This decouples the interpretation from the structure, but still relies on mutation. Minus one point for mutation, and minus one for the fact that Visitor is incredibly crufty. For example, to get the depth of our tree structure above, we have to implement a TreeDepthVisitor. A good IDE that generates boilerplate for you is definitely recommended if you take this approach.

On the plus side, both of these patterns provide some enforcement of the exhaustiveness of the pattern match. For example, if you add a new term type, the Interpreter pattern will enforce that you implement the interpretation method. For Visitor, as long as you remember to add a visitation method for the new term type to the visitor interface, you will be forced to update your implementations accordingly.

The Bad: Instanceof

An obvious approach that’s often sneered at is runtime type discovery. A quick and dirty way to match on types is to simply check for the type at runtime and cast:

public static int depth(Tree t) {
  if (t instanceof Empty)
    return 0;
  if (t instanceof Leaf)
    return 1;
  if (t instanceof Node)
    return 1 + max(depth(((Node) t).left), depth(((Node) t).right));
  throw new RuntimeException("Inexhaustive pattern match on Tree.");
}

There are some obvious problems with this approach. For one thing, it bypasses the type system, so you lose any static guarantees that it’s correct. And there’s no enforcement of the exhaustiveness of the matching. But on the plus side, it’s both fast and terse.

The Good: Functional Style

There are at least two approaches that we can take to approximate pattern matching in Java more closely than the above methods. Both involve utilising parametric polymorphism and functional style. Let’s consider them in order of increasing preference, i.e. less preferred method first.

Safe and Terse – Disjoint Union Types

The first approach is based on the insight that algebraic data types represent a disjoint union of types. Now, if you’ve done any amount of programming in Java with generics, you will have come across (or invented) the simple pair type, which is a conjunction of two types:

public abstract class P2<A, B> {
  public A _1();
  public B _2();
}

A value of this type can only be created if you have both a value of type A and a value of type B. So (conceptually, at least) it has a single constructor that takes two values. The disjunction of two types is a similar idea, except that a value of type Either<A, B> can be constructed with either a value of type A or a value of type B:

public final class Either<A, B> {
  ...
  public static <A, B> Either<A, B> left(A a) { ... }
  public static <A, B> Either<A, B> right(B a) { ... }
  ...
}

Encoded as a disjoint union type, then, our Tree data type above is: Either<Empty, Either<Leaf, Node>>

Let’s see that in context. Here’s the code.

public abstract class Tree {
  // Constructor private so the type is sealed.
  private Tree() {}

  public abstract Either<Empty, Either<Leaf, Node>> toEither();

  public static final class Empty extends Tree {
    public <T> T toEither() {
      return left(this);
    }

    public Empty() {}
  }

  public static final class Leaf extends Tree {
    public final int n;

    public Either<Empty, Either<Leaf, Node>> toEither() {
      return right(Either.<Leaf, Node>left(this));
    }

    public Leaf(int n) { this.n = n; }
  }

  public static final class Node extends Tree {
    public final Tree left;
    public final Tree right;    

    public Either<Empty, Either<Leaf, Node>> toEither() {
      return right(Either.<Leaf, Node>right(this));
    }

    public Node(Tree left, Tree right) {
      this.left = left; this.right = right;
    }
  }
}

The neat thing is that Either<A, B> can be made to return both Iterable<A> and Iterable<B> in methods right() and left(), respectively. One of them will be empty and the other will have exactly one element. So our pattern matching function will look like this:

public int depth(Tree t) {
  Either<Empty, Either<Leaf, Node>> eln = t.toEither();
  for (Empty e: eln.left())
    return 0;
  for (Either<Leaf, Node> ln: t.toEither().right()) {
    for (leaf: ln.left())
      return 1;
    for (node: ln.right())
      return 1 + max(depth(node.left), depth(node.right));
  }
  throw new RuntimeException("Inexhaustive pattern match on Tree.");
}

That’s terse and readable, as well as type-safe. The only issue with this is that the exhaustiveness of the patterns is not enforced, so we’re still only discovering that error at runtime. So it’s not all that much of an improvement over the instanceof approach.

Safe and Exhaustive: Church Encoding

Alonzo Church was a pretty cool guy. Having invented the lambda calculus, he discovered that you could encode data in it. We’ve all heard that every data type can be defined in terms of the kinds of operations that it supports. Well, what Church discovered is much more profound than that. A data type IS a function. In other words, an algebraic data type is not just a structure together with an algebra that collapses the structure. The algebra IS the structure.

Consider the boolean type. It is a disjoint union of True and False. What kinds of operations does this support? Well, you might want to do one thing if it’s True, and another if it’s False. Just like with our Tree, where we wanted to do one thing if it’s a Leaf, and another thing if it’s a Node, etc.

But it turns out that the boolean type IS the condition function. Consider the Church encoding of booleans:

true  = λa.λb.a
false = λa.λb.b

So a boolean is actually a binary function. Given two terms, a boolean will yield the former term if it’s true, and the latter term if it’s false. What does this mean for our Tree type? It too is a function:

empty = λa.λb.λc.a
leaf  = λa.λb.λc.λx.b x
node  = λa.λb.λc.λl.λr.c l r

You can see that this gives you pattern matching for free. The Tree type is a function that takes three arguments:

  1. A value to yield if the tree is empty.
  2. A unary function to apply to an integer if it’s a leaf.
  3. A binary function to apply to the left and right subtrees if it’s a node.

The type of such a function looks like this (Scala notation):

T => (Int => T) => (Tree => Tree => T) => T

Or equivalently:

(Empty => T) => (Leaf => T) => (Node => T) => T

Translated to Java, we need this method on Tree:

public abstract <T> T match(F<Empty, T> a, F<Leaf, T> b, F<Node, T> c);

The F interface is a first-class function from Functional Java. If you haven’t seen that before, here it is:

public interface F<A, B> { public B f(A a); }

Now our Tree code looks like this:

public abstract class Tree {
  // Constructor private so the type is sealed.
  private Tree() {}

  public abstract <T> T match(F<Empty, T> a, F<Leaf, T> b, F<Node, T> c);

  public static final class Empty extends Tree {
    public <T> T match(F<Empty, T> a, F<Leaf, T> b, F<Node, T> c) {
      return a.f(this);
    }

    public Empty() {}
  }

  public static final class Leaf extends Tree {
    public final int n;

    public <T> T match(F<Empty, T> a, F<Leaf, T> b, F<Node, T> c) {
      return b.f(this);
    }

    public Leaf(int n) { this.n = n; }
  }

  public static final class Node extends Tree {
    public final Tree left;
    public final Tree right;    

    public <T> T match(F<Empty, T> a, F<Leaf, T> b, F<Node, T> c) {
      return c.f(this);
    }

    public Node(Tree left, Tree right) {
      this.left = left; this.right = right;
    }
  }
}

And we can do our pattern matching on the calling side:

public int depth(Tree t) {
  return t.match(constant(0), constant(1), new F<Node, Integer>(){
    public Integer f(Node n) {
      return 1 + max(depth(n.left), depth(n.right));
    }
  });
}

This is almost as terse as the Scala code, and very easy to understand. Everything is checked by the type system, and we are guaranteed that our patterns are exhaustive. This is an ideal solution.

By the way, if you’re wondering what constant(0) means, it’s a method that returns a function F<A, Integer> that always returns 0, ignoring the argument.

Conclusion

With some slightly clever use of generics and a little help from our friends Church and Curry, we can indeed emulate structural pattern matching over algebraic data types in Java, to the point where it’s almost as nice as a built-in language feature.

So throw away your Visitors and set fire to your GoF book.

Advertisement

Heterogeneous Lists and the Limits of the Java Type System

Today, we’re going on a journey. It is a sojourn to the outer limits of the expressiveness of the Java type system, and to the edge of what can be considered sane programming. This is definitely one for the power users. You will need a firm grasp of the Java language, and an iron constitution for type annotations. But the reward will be something far greater than any treasure: understanding, entertainment, and perhaps even enlightenment. Remember that we choose to do these things in Java, not because they are easy, but because they are hard. Now then, to the ships.

A Most Versatile Vessel

In Java, we can create a list that contains values of type A, by constructing a value of type List<A>. The type system will enforce that each element in the list is in fact of type A. But sometimes we want lists of values that aren’t necessarily of the same type. Normally, for such a purpose, we would use a heterogeneous list, which in Java is just the raw list type List<?> or List<Object>. Since every class in Java is a subclass of Object (and now that we have autoboxing), such a list can contain any Java value. There are many kinds of situation where this would be necessary. For example, a row of database results will comprise values that are not all of the same type.

However, there’s a problem with the raw list approach. In using the List<?> type, we are dispensing with the type system. When you get a value from the list, how do you know what it is? How do you know which operations it supports? Well, you will have to defer that discovery until runtime, and use explicit type casting. Most will shrug at this and say: “So what?” After all, this is what we did anyway, before generics. Ah, but what if we don’t have to? Can we create generic heterogeneous collections that are type-safe? Yes, we can. Sort of.

Products of Types

What we would like to see is if it’s possible to declare some constraints on the types of a heterogeneous collection, to achieve essential type-safety while maintaining the extensibility of a list. Of course, it’s easy to create types that are the product of two or more types:

public abstract class P2<A, B> {
  public abstract A _1();
  public abstract B _2();
}

But the length of this kind of product is as fixed as the length of a string in Pascal. It isn’t extensible, so it’s more like a type-safe heterogeneous array than a list. If you want products of different lengths, you will need to declare separate classes for P3<A, B, C>, P4<A, B, C, D>, etc. What we’re trying to achieve is a product of arbitrary length, whose length might even vary at runtime. There’s no reason we couldn’t create products of products in a chain, like P2<A, P2<B, P2<C, D>>>, and this is more or less the approach that we will take.

Introducing HList

To achieve our goal, we’re going to implement linked lists in the type system. Let’s remind ourselves what a linked list looks like. A List<T> is essentially either the empty list or a value of type T paired with a List<T>. In Java, using the List<A> type from Functional Java, an unsafe heterogeneous list might be constructed in a manner like the following:

List<?> x = cons("One", cons(2, cons(false, nil()));

The cons method constructs a list, and the nil method returns the empty list. With just these two methods, we can create any homogeneous list. A list has two methods to access its members, head() which returns the first element, and tail() which returns the rest of the list. Getting the head or tail of the empty list is an error at runtime.

Let’s now take a step up into the type system, and say that a list of types is either the empty list or a type paired with a list of types. This gives rise to our heterogeneous list type:

public abstract class HList<A extends HList<A>> {
 private HList() {}

 private static final HNil nil = new HNil();

 public static HNil nil() {
   return nil;
 }

 public static <E, L extends HList<L>> HCons<E, L> cons(final E e, final L l) {
   return new HCons<E, L>(e, l);
 }

 public static final class HNil extends HList<HNil> {
   private HNil() {}
 }

 public static final class HCons<E, L extends HList<L>> extends HList<HCons<E, L>> {
   private E e;
   private L l;

   private HCons(final E e, final L l) {
     this.e = e;
     this.l = l;
   }

   public E head() {
     return e;
   }

   public L tail() {
     return l;
   }
 }
}

That’s not a lot of code, and it’s all relatively straightforward Java. The HList class is parameterised with a parameterised subclass of itself. There are only two concrete subclasses of HList that can possibly occupy that slot: the type HNil and the type constructor HCons. These represent the empty list and the list constructor, respectively. HCons takes two type parameters, the first representing the first element of the list, and the second being another HList, allowing us to form a chain of them. HNil does not take type parameters, so it terminates the chain.

As with regular old lists, you can access the head() and tail() of the list. Note, however, that the fact that you cannot get the head or tail of the empty list is now enforced by the type system. There’s a nil method to get the empty list, and a cons method to construct a nonempty list, just like with regular lists.

Here’s an example of how we would construct a heterogeneous list using this new type:

HCons<String, HCons<Integer, HCons<Boolean, HNil>>> x = cons("One", cons(2, cons(false, nil()));

This is more verbose than the unsafe version before, but not by much. Obviously, the HList example assumes a static import of HList.cons and the List<?> example assumes a static import of List.cons. Using the type-safe version is, however, much nicer. Compare these two contrived examples:

if (x.tail().tail().head()) {
  return x.head().length() == x.tail().head();
}

if ((boolean) x.index(3)) {
  return ((String) x.head()).length() == (int) x.index(2);
}

The latter, of course, offers no static guarantees and may throw ClassCastExceptions, or we might inadvertently get the head or tail of the empty list at runtime. The former will always work as long as it compiles, guaranteed.

Concatenating HLists

Now let’s do something more interesting with these lists. Notice that the cons methods for both type-safe and unsafe lists prepend an element to a list rather than appending. Sometimes we want to append a list to the end of another. This is unsurprisingly uncomplicated for unsafe lists:

List<?> c = a.append(b);

Behind the scenes, we can think of append as reversing the first list and consing each element to the second list in reverse order. Doing that for HList is a little more involved. We have to construct a chain of types in exactly the right way, at compile-time.

Appending an HList to another is a function that takes two HList-valued arguments and returns an HList. Using first-class functions from Functional Java, the append operation for HLists of specific types L and R, would be a function of the following type:

F2<L extends HList<R>, L extends HList<L>, LR extends HList<LR>>

Where LR is the type of the concatenated HList. Now, since we necessarily have the two arguments, we know the specific types of L and R. Since Java doesn’t have type inference, it cannot automatically figure out the specific type of LR. We will have to supply it as type annotation. Not to worry. Even though Java doesn’t infer types, it can be coerced into doing some type arithmetic. All we have to do is a little inductive reasoning.

Types as Formulae

According to the Curry-Howard isomorphism, a program is a proof, and the hypothesis that it proves is a type for the program. In this sense, Java’s type system is a kind of crude theorem prover. Put another way, a type is a predicate, and values of that type represent the terms for which the predicate holds. The function type above therefore asserts that for any two HLists, L and R, there exists some program to derive the HList LR. The function type by itself does not put any constraints on LR, however. It can be derived by any function, not just the concatenation function. We will remedy that presently. We need a formula that states that the two types L and R imply a third type LR which is the HList concatenation of L and R, given some concatenation function. Here is the type that represents that formula:

public static final class HAppend<L, R, LR> {
    private final F2<L, R, LR> append;

    private HAppend(final F2<L, R, LR> f) {
      append = f;
    }

    public LR append(final L l, final R r) {
      return append.f(l, r);
    }
}

At this point, HAppend is still just a hypothesis without evidence. Remember that a value of a type is proof of the formula that it represents. So we will need to supply two proofs in the form of constructors for values of this type; one for the base case of appending to the empty list HNil, and another for the case of appending to an HCons. The base case is easy. Appending anything to the empty list should result in that same thing. So the HAppend constructor for appending to the empty list looks like this:

    public static <L extends HList<L>> HAppend<HNil, L, L> append() {
      return new HAppend<HNil, L, L>(new F2<HNil, L, L>() {
        public L f(final HNil hNil, final L l) {
          return l;
        }
      });
    }

The case for the nonempty list is not quite as easy. Consider its type:

    public static <X, A extends HList<A>, B, C extends HList<C>, H extends HAppend<A, B, C>>
                         HAppend<HCons<X, A>, B, HCons<X, C>> append(final H h)

Read the return type first. This returns an HAppend that appends some B to an HCons<X, A>. The type of the head of the first list (X) becomes the type of the head of the concatenated list. The tail of the concatenated list is C. The type constraints state that C must be an HList, and that there must exist some way to append B (the second list) to A (the tail of the first list) so that they make C. We must supply proof that this last constraint holds, and you’ll see that such a proof is in fact supplied as an argument (in the form of the value h).
What this is saying is that, given the premise that A and B can be concatenated, the concatenation of HCons<X, A> and B can be inferred. A value of type HAppend<A, B, C> is precisely proof of the hypothesis that A and B can be concatenated, since there are only these two cases and we’ve supplied a proof for both. In other words, if we can append to the empty list, then that’s proof enough that we can append to a list of one element, which proves that we can append to a list of two elements, and so on. Given this, we can construct a chain of proofs. This concatenated proof, then, is a function that concatenates lists of the corresponding types.

OK, so how do we use this? Well, here’s an example program that appends one list to another:

public class HList_append {
  public static void main(final String[] args) {
    // The two lists
    final HCons<String, HCons<Integer, HCons<Boolean, HNil>>> a =
      cons("Foo", cons(3, cons(true, nil())));
    final HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>> b =
      cons(4.0, cons("Bar", cons(new Integer[]{1, 2}, nil())));

    // A lot of type annotation
    final HAppend<HNil, HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>>,
      HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>>> zero = append();
    final HAppend<HCons<Boolean, HNil>, HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>>,
      HCons<Boolean, HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>>>> one = append(zero);
    final HAppend<HCons<Integer, HCons<Boolean, HNil>>, HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>>,
      HCons<Integer, HCons<Boolean, HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>>>>> two = append(one);
    final HAppend<HCons<String, HCons<Integer, HCons<Boolean, HNil>>>,
      HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>>,
      HCons<String, HCons<Integer, HCons<Boolean, HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>>>>>>
      three = append(two);

    // And all of that lets us append one list to the other.
    final HCons<String, HCons<Integer, HCons<Boolean, HCons<Double, HCons<String, HCons<Integer&#91;&#93;, HNil>>>>>>
      x = three.append(a, b);

    // And we can access the components of the concatenated list in a type-safe manner
    if (x.tail().tail().head())
      System.out.println(x.tail().tail().tail().tail().tail()[1] * 2); // 4
  }
}

Holy pointy brackets, Batman! Do we really need all of that? Well, look at what it’s doing. It’s constructing a concatenation function of the appropriate type, by supplying the premise at each step. If this seems mechanical, then that’s because it is. There is only one possible implementation for the HAppend we need, but Java does not have any mechanism for figuring this out, nor does it provide a facility for the programmer to tell it how.
Contrast that to Scala. The above is a clear example of where Scala’s implicit arguments come in handy. If we import this to Scala, we can make both of the append functions implicit, and we can further make the H argument to the append function for nonempty lists implicit as well. There can be only one possible implementation of each function, so it can be declared once and used implicitly wherever proofs of the corresponding types are required. Jesper Nordenberg has implemented an HList library for Scala that demonstrates this well. With implicits and Scala, the whole middle section of our program is condensed from 12 lines of type annotations to just:

 val x = a.append(b)

Now, if you’re really into this Java stuff, you’re probably thinking: “implicits are just dependency injection”. Well, in a sense, you would be right. Both dependency injection and inheritance are degenerate forms of implicits. However, there is currently no dependency injection framework for Java that can abstract over type constructors such that it provides injection of parameterised types with injection of type parameters also. If you can prove me wrong, by all means send me evidence in the form of working code.

Conclusion

Clearly, Java is not very useful for this kind of type-safe programming. I was actually quite surprised that you can do this in Java at all, but we’ve definitely hit the outer boundary of what can be considered reasonably expressible.

The code you’ve seen in this article uses the new HList package that was released with Functional Java 2.16. And is based on the Haskell HS library by Oleg Kiselyov.