Being in bed with a little fever, I thought it might be a good time for a little easy work on functional programming in Java.
Haskell envy
One of the things functional programmers often use is algebraic datatypes. For instance, in Haskell you would define a binary tree as such:
type tree = Empty
| Leaf of int
| Node of tree * tree
This says that a tree is either the Empty tree, or a Leaf that carries an integer value, or a Node that carries two subtrees.
The next thing is to define functions, such as tree height; the nice thing is that the functions are then defined by cases. It’s kind of fun:
height :: Tree -> Int
height Empty = 0
height (Leaf n) = 1
height (Node l r) = 1 + max (height l) (height r)
This says that an Empty tree has height 0, a Leaf has height 1, and a Node has height that is the maximum height of its subtrees, plus 1. Now we could have fun defining all sorts of other functions, like the contour (the list of the integers of all leafs), search for a particular value, addition of elements, and so on.
Additionally, when working in languages like Haskell, the compiler makes sure that when we define a function by cases, the program will not compile unless we remembered to define all cases.
This sort of data structures have all sort of applications; an obvious one is representing syntax trees, that is the output of a parser. Another one is representing the syntax rules themselves.
We can do it!
What’s to do if you have to work in a simpler language like Java? Do we have to give up the fun of algebraic data types? Of course not! It’s possible to define such structures in Java, even though it will take one or two orders of magnitude more lines of code.
Step zero: define the structure
public abstract class Tree {}
public class EmptyTree extends Tree {}
public class Leaf extends Tree {
public Leaf(int value) {
}
}
public class Node extends Tree {
public Node(Tree left, Tree right) {
}
}
Now we can create our trees with the following deliciously clumsy syntax:
Tree tree = new Node(
new Node(new Leaf(0), new EmptyTree()),
new EmptyTree());
We could make it slightly less verbose with static functions.
Step one: define height
The easy way to add a function is to define it abstractly in Tree. The compiler then forces us to define it in all Tree subclasses (in all cases). First a test:
@Test
public void heightOfSimpleTree() throws Exception {
Tree tree = new Node(
new Node(new Leaf(0), new EmptyTree()),
new EmptyTree());
assertEquals(3, tree.height());
}
Then the implementation:
public abstract class Tree {
public abstract int height();
}
public class EmptyTree extends Tree {
public int height() {
return 0;
}
}
public class Leaf extends Tree {
public Leaf(int value) {
}
public int height() {
return 1;
}
}
public class Node extends Tree {
private final Tree left;
private final Tree right;
public Node(Tree left, Tree right) {
this.left = left;
this.right = right;
}
public int height() {
return 1+ Math.max(left.height(), right.height());
}
}
(I told you this was going to be verbose. You were warned :-)
Step two: respect the OCP, son!
Now we could go on defining all kinds of functions on trees this way; but this would mean that for every new function, we need to change all of our classes. That won’t do; we don’t want to keep changing and adding to the same old files. We want to close the Tree classes for modification, but keep them open for extension; this is the open/closed principle. What can we do?
A pattern to the rescue. Have you ever wondered where it’s reasonable to use Visitor? Well, this is it. As usual, we start with a test:
@Test
public void heightWithVisitor() throws Exception {
Tree tree = new Node(
new Node(new Leaf(0), new EmptyTree()),
new EmptyTree());
Visitor height = new Height();
assertEquals(3, tree.accept(height));
}
The implementation of visitor can be:
public abstract class Tree {
public abstract int accept(Visitor visitor);
}
public class EmptyTree extends Tree {
public int accept(Visitor visitor) {
return visitor.visitEmptyTree();
}
}
public class Leaf extends Tree {
private final int value;
public Leaf(int value) {
this.value = value;
}
public int accept(Visitor visitor) {
return visitor.visitLeaf(value);
}
}
public class Node extends Tree {
private final Tree left;
private final Tree right;
public Node(Tree left, Tree right) {
this.left = left;
this.right = right;
}
public int accept(Visitor visitor) {
return visitor.visitNode(left, right);
}
}
Note that each tree subcase provides the visitor with all the information they contain. This way we avoid getters, which is nice. The definition of Height is very similar to the Haskell example:
public class Height implements Visitor {
public int visitEmptyTree() {
return 0;
}
public int visitLeaf(int value) {
return 1;
}
public int visitNode(Tree left, Tree right) {
return 1 + Math.max(left.accept(this), right.accept(this));
}
}
The nice thing is that now the Height function lives in its own little object. We were able to decouple it from the Tree classes.
We still can’t forget to define a case, as the compiler will force us to implement all three methods of Visitor.
Step three: generics
Of course, the big problem with this Visitor implementation is that it only works for functions that return integers. We can solve this with Java generics:
public interface Visitor<T> {
T visitEmptyTree();
T visitLeaf(int value);
T visitNode(Tree left, Tree right);
}
public abstract class Tree {
public abstract <T> T accept(Visitor<T> visitor);
}
public class EmptyTree extends Tree {
public <T> T accept(Visitor<T> visitor) {
return visitor.visitEmptyTree();
}
}
// etc.
The other way to solve the genericity problem would be to define the Height visitor as a stateful object, that has a int result() method that is not part of the Visitor interface. But we’ll leave that to some other time.
A delightful little book on this very subject is A Little Java, A Few Patterns by Matthias Felleisen and Daniel P. Friedman. In fact I think I learned the meaning of Visitor by reading this book! The authors wrote a number of books on Lisp and Scheme in a similar vein; the first one was The Little Lisper and it takes a very unusual approach to teaching.
Hope it comes in handy!
