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:

- A value to yield if the tree is empty.
- A unary function to apply to an integer if it’s a leaf.
- 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.

Interesting stuff, although I see your “Church encoding” approach as really just a variant of the Visitor pattern in disguise (rename “match” with “accept” and arguments “a”, “b” and “c” with “visitEmpty”, “visitNode” etc). A more traditional visitor would actually often be more concise, particularly when you have to do a custom thing for each branch in your pattern, and you can’t easily compose it from other functions in your library (as you do with “constant”). In such cases, you’d need just one visitor anonymous class as opposed to three “F” anonymous classes, which would be a bit less noisy syntactically.

On the other hand, if you do use functions like constant(), there is no indication of which function corresponds to which case other than by argument position; which gets constant(0) and which gets constant(1)? In a traditional visitor, the method name can indicate which case you are in.

So my view is that the traditional visitor is still a better approach to pattern matching in Java in many cases, flawed though it is.

I did actually like the “foreach” approach, though. I think it would be a handy supplement to offering a visitor. A refinement that might make it a little more readable would be to have three methods on Tree: getEmpty(), getNode() and getLeaf(), returning Option[Empty], Option[Node], Option[Leaf] respectively, where Option is an Iterable.

Matt,

It occurs to me that perhaps “visitor” is just a degenerate (specialised?) case of the Church encoding. I like your Option approach, although it doesn’t guarantee disjointness.

I’ve had the last encoding in my Sasa C# library for awhile now; here’s the <a href="Either type. There are a few other classes where I exploit this encoding as well.

I have yet to see a convincing example of case classes that cannot be implemented more simply and more elegantly with simple polymorphism, and this one is no exception.

How about a base interface BaseNode with a depth() method on it and

class Empty implements BaseNode {

public int depth() { return 0; }

}

class Leaf implements BaseNode {

public int depth() { return 1; }

}

class Node implements BaseNode {

public int depth() { return 1 + Max(mLeft.depth(), mRight.depth()); }

}

It’s statically safe, open for extension and properly encapsulates the logic of each computation where it belongs instead of spreading it over several classes.

So you’ll have three separate mutually isomorphic inheritance hierarchies (with the isomorphism enforced by the programmer). I’ve been down that path. It leads to TotalLengthSummingTreeNode, TotalLengthSummingTreeLeaf, TotalLengthSummingEmptyTree, ClassNameLengthMaximizingTreeNode, etc.

Not, just one hierarchy: BaseNode and below, the three subclasses. I would draw the graph but my spaces will probably be eaten :-)

Compare this to the case class approach that requires the class that does the match to know about *all* the concrete implementations that it’s comparing against. When you add a new class, you need to remember to go add that switch case or your code will break.

In comparison, the polymorphic approach only requires you to implement that new class (which you must do anyway) and that’s all.

The problem with case classes is that the classes that do the switch become the point of convergence of a lot of classes, which increases coupling terribly.

OK, so you’ll have three classes with every conceivable method you would ever want to invoke on trees. Oh, except one. How do you add it? Oh, and that other one. Have to add that too.

Really, read the intent section of the Visitor pattern in your DP book (if you haven’t burned it already, tee hee). There is a reason why structural pattern matching is desirable, and it’s that class hierarchies are not in fact open to extension.

Oh, one thing. Pattern matching is for sealed types. You necessarily will want to know about all the concrete cases that you’re comparing against because you want your patterns to be exhaustive. I suppose we would want an “otherwise” case though. We could employ partial application for that.

You have to add switch cases to your class as well so case classes are no improvement for that part of your argument. Actually, they are worse because they require modifications of your code in two different locations instead of one.

For example, if you add a new class Leaf2 to your graph hierarchy, here is what you need to add:

Case classes:

– New class

– New case in the switch/case

Polymorphism:

– New class

Case classes also violate encapsulation because you are now forced to implement a method that will deconstruct your class, so for every private field you add to your class, you need to update your deconstructor as well or it won’t take part in switching.

I wrote more detailed thoughts on the flaws of case classes here:

http://beust.com/weblog/archives/000490.html

Cedric, I read your critique of pattern matching before and I disagree with it strongly. I think you’re entirely missing the point of algebraic data types.

I will never want to add a new class Leaf2 to this hierarchy. It’s not part of the algebra and it never will be.

Apocalisp,

FYI, Cedric’s objection to ‘case classes’ is deeply embedded in a thorough misunderstanding of the purpose of algebraic data types. It might be best to approach the discussion in this manner.

*and closed sum types (ie Scala’s sealed keyword, Haskell’s data keyword).

Tony, what if I actually understand algebraic data types quite well and still maintain my criticism of case classes as a step back in terms of software engineering?

It’s not a shot in the dark. You’ve demonstrated it quite emphatically. I’m uninterested in working this out. Hopefully Apocalisp can.

Not all that interested. I was just looking for a nicer way of deconstructing disjoint union types in Java. It’s not all that structural, and I don’t think it can be. I’m genuinely uninterested in arguments against language features, especially useful ones like structural decomposition.

Furry nuts. Don’t blame you :)

You do not understand. There is so much misinformation in this thread, that I feel compelled to address it:

Algebraic data types (ADT) and OO are duals of each other. ADTs are closed under cases (hard to add new cases), and inheritance is closed under operations (hard to add new operations). This is well known, and any argument you care to make for the superiority of OO, has a dual demonstrating the superiority of ADTs and pattern matching. This whole debate is dead in the water, and has been for some time.

Visitors are an attempt to encode ADTs and pattern matching to OO languages, as is the technique described in apocalisp’s post (though OO languages would just be better off implementing first-class messages). There are corresponding techniques in functional languages to simulate ad-hoc polymorphism (the polymorphism OO languages provide).

Until Scala came on the scene, functional languages have actually had the advantage here, because OCaml has polymorphic variants and Haskell has type classes, which handle extension in the direction that ADTs and pattern matching are typically weak in. They both admit solutions to the expression problem as a result. Scala was the first production OO language that solved the expression problem, and all other existing OO languages are too weak to admit safe solutions.

And Casper, academia does not want “everything open to extension”, they are driven to research extension by real-world demands. Extension is an important aspect of software engineering, as it promotes code reuse, which reduces bugs.

Academia seeks to improve the

safeextensibility of solutions, so that practitioners can provide those guarantees you speak of, while still permitting extensions.While I understand that algebraic data types represent a disjoint union of types, they don’t allow to model cases where you want to add new types. This has been documented long time ago by Philip Wadler and is known as the expression problem: http://www.daimi.au.dk/~madst/tool/papers/expression.txt

Visitor and Composite pattern can’t solve it, neither algebraic data types.

It’s also addressed in Scala: http://www.scala-lang.org/docu/files/TheExpressionProblem.pdf

Maybe algebraic data types are not the most appropriate solution to model cases where you need your structure to be extensible.

Karel,

Algebraic data types are appropriate for modeling an algebra which is closed. It can be open to extension in the sense that cases can take type parameters, but you really don’t want cases to be added.

That was exactly my point: algebraic data types are *not* an appropriate approach for the kind of problem that you describe in this post (and as a corollary, case classes are the wrong choice for this as well).

Sorry, but yes they are. It’s exactly that kind of problem.

I find the initial introduction to case classes insufficient for having the average Java developer grasp the matter. As such, reading this I was thinking “but a pair class is not type safe?” and “but we have polymorphism which encapsulates branching?”.

Also, I wonder whether this boils down to academia wanting to have everything open for extension while practitioners desires the opposite, as they often can’t make certain guarantees. This has leaked into languages before, i.e. Java’s virtual-by-default behavior.

To that effect, I think Cedric has a point which you are not treating particularly professionally from a software development point of view.

Casper,

This is a blog post, not an extensive thesis on algebraic data types.

I don’t see how a pair is not type-safe.

If I could give a single piece of advice to “the average Java developer”, as you put it, it would be: Don’t use ad-hoc polymorphism by inheritance so much. Use parametric polymorphism instead. Indeed, even where you have to use subclassing (e.g. for types that are intended to be algebraic), you only need one abstract method (the match method).

I may be missing Cedric’s point. To me it seems that he’s railing against a language feature that he doesn’t understand, in favour of those with which he’s developed some expertise.

Cedric doesn’t have a point because he doesn’t realise that case classes have nothing to do with anything related to the topic at hand. If his problem is with closed versus open types and how it relates to The Expression Problem, then his problem is with the absence or presence of the sealed keyword in terms of Scala. This issue has nothing at all to do with Scala’s case classes. Cedric’s point is rightfully dismissed.

You assert that the visitor pattern relies on mutation, but I don’t see how. I’ve used the visitor pattern many times while programming with immutable data in Java.

Neal,

As presented in the GoF book, the visit and accept methods are void. I suppose they don’t really have to be, but if they aren’t then you end up with something very similar to what I’ve presented here.

This is pretty neat. The only weakness I can see is that while your solution is both safe and exhaustive, it is not at all terse in cases where the ADT has many possible forms, because the match method always requires you to handle all of them. All pattern-matching syntaxes I’ve seen allow omitting some of the cases and specifying a default case, and with the visitor pattern one can extend an abstract class containing empty (or null-returning) implementations of all the visitor methods, and only implement the methods one cares about.

Still, many of the most important ADTs I can think of only come in 2 or 3 forms, and for those this seems like a quite elegant approach.

Before throwing away the GoF-book, maybe you should have read it first?

This decouples the interpretation from the structure, but still relies on mutation.

The Visitor pattern does not rely on mutation! It’s a pattern, you are allowed to return values, so you can apply the usual functional style of keep-your-methods-pure.

Heck, only because the C++-examples use void as return type, you believe this is an unavoidable part of the pattern? The Smalltalk example in the GoF-book

doesreturn a result state!For Visitor, as long as you remember to add a visitation method for the new term type to the visitor interface, (…)

“As long as you remember”? You cannot forget it, you must provide an implementation of the accept-method on the new term type!

Pattern matching in Scala may have advantages over the visitor pattern (you can dispatch not only on types, but also on the same type with different values) but for the purpose described in your article, the visitor pattern is just as good as pattern matching.

Here is my understanding. I would be interested in comments regarding it’s validity:

The purpose of the fold or match methods is for pattern matching–which my understanding should not expose the

constructor, only those items wrapped by the constructor.

Tree is the type. Empty, Leaf, Node are constructors. Which means they should be private since nothing should be able to work with them because they are not types to be worked with.

So, the “callbacks” would have the unwrapped values as parameters and the pattern matching code might look something like:

public abstract T match(P1 a, F b, F<P2, T>();

And the calling side would be something like:

public int depth(Tree t) {

return t.match(P.p(0), constant(1), new F<P2, Integer>(){

public Integer f(Tree left, Tree right) {

return 1 + max(depth(left), depth(right));

}

});

}

Pingback: Structural Pattern Matching using Exceptions « shahriar

Please fix the CSS style. Thanks!

Hi, it’s impossible to read this blog, the end of the lines disappear behind the frame of the page.

Or is it just me? using Chrome on Win7

It’s not just you. WordPress has somehow managed to mangle every post and I’m not sure how to fix it. I started a new blog at blog.higher-order.com basically because WordPress is really terrible.