Catamorphisms for Java developers

In this article we will examine in depth a useful concept, the catamorphism, commonly used in functional languages but rarely seen in Java. Catamorphisms are very easy to implement, and typically only require a few lines of Java code. Those few lines of code add significant power to your internal APIs, effectively introducing compiler enforced, exhaustive structural pattern matching, the kind that can banish frustrating and difficult to stop bugs that sneak in through complex if / then / else spaghetti code.

Simple concept, complex word

The word Catamorphism, formed from the Greek words for downwards (cata) and transformation (morphism), probably sounds alien to most Java developers. The definition posited on wikipedia that

In functional programming,catamorphisms provide generalizations of folds of lists to arbitrary algebraic data types, which can be described as initial algebras

will probably be utterly unintelligible to most. Which is a pity as catamorphisms are both an incredibly useful and reasonably simple concept that can be used to produce code that is both cleaner (subjectively) and safer / with less bugs (objectively).

The Lambda Visitor Pattern

While the term catamorphism may not have entered mainstream Java lexicon, the codification of the principal as a Gang of Four design principle has. The visitor pattern defines a cumbersome and complex way of implementing catamorphisms (which may be why it is not so widely used). Fortunately with arrival of Java 8 implementing the visitor pattern (and catamorphisms more generally) has gotten a lot simpler.

The catamorphism for Optional

When implementing a catamorphism, the goal is provide access to the key structural information of a type in a safe an exhausitive manner. Java 8’s Optional class can be in one of two states

Present (with some data)

Empty (with no data)

The catamorphism for Optional can be written in terms of two functions

Present : a j.u.Function that accepts the Optional’s value

Empty : a j.u.Supplier that is executed to retrieve a value

Callers of the catamorphism provide both lambda’s (or other implementations) of both function types, only one of which is selectively executed depending on the state.

We can define the cata-morphism for Optional simply as follows

This is the catamorphism implementation for Optional in cyclops-react Optionals companion class

To use the catamorphism we supply the Optional to process and our functions to execute. In the code below a will hold the value returned by our supplier, and b the result of the execution of our function (where the input parameter is the value of the Optional 10).

a will be -1, b will be 20

Pattern matching on Optional

It turns out that when we use our catamorphism for Optional we are doing something very similar to pattern matching in functional languages (and dual paradigm languages like Scala). That is, we are deconstructing the Optional instance, and selecting the appropriate case / function to execute based on it’s internal state.

Scala pattern matching code for Option

The Scala code to pattern match on Option is ultimately very similar to our visitor / catamorphism code for Optional.

Why is this good?

Pattern matching in Scala isn’t just a more powerful version of Java’s Switch Statement. The Scala compiler is also able to detect if all possible cases from a deconstruction have be covered by the developer and to warn or error if they have not.

Similarly, if Java developers make use of catamorphisms the compiler will force them to provide implementations for all possible states the Optional (or type under scrutiny) has.

Javac would help us if we used our visit method!

Photo by Kristopher Roller on Unsplash

Getters break encapsulation

Scala has the concept of case classes. Case classes are really simple classes with immutable fields that can be defined really succinctly.

We can define a similar class in Java, which while a little larger is also very explicit about what the compiled classes structure will actually be.

Once created, however usage is very similar

Scala case class usage

Java case class usage

Except in one regard, in the abscence of a catamorphism Java implementation for Book we can pattern match in Scala but not in Java

But this is easily fixed

In Java, we now have the additional option of making our case class members private and forcing all access through the catamorphism. The benefits of doing so for a simple class like our Book example are minimal, but as we have seen with Optional even a little additional complexity means errors can begin to seep into our code base. Let’s see this in action, by introducing two new subclasses of Book — Fiction and Nonfiction.

Either Fiction or Nonfiction

We can refactor our Book class making a couple of changes

1. We make Book an abstract class, as we now have two concrete types (Fiction and Nonfiction instead)
2. We define the two sub-types (Fiction and Nonfiction)
3. We make all fields private (to keep the code that uses our Book instances simple!)

There are a few notable properties of this class, the only concrete types of Book that are definable are Fiction and NonFiction. This is enforced by the private constructor. Additionally all access to the internal state or structure of our Book instance is controlled via our original catamorphism.

How do we handle fiction and nonficton differently

Now we have two types of Books we may be tempted to process them via the traditional Java if / then / else statement.

Even for such a relatively trivial example, if / then / else can cause bugs : note the semicolon! a is alway 1

A better approach is to define another catamorphism that folds over the possible types of Books. The implementation for this would look very like our implementation for Optional, except that we would accept two single parameter functions. One would receive Fiction instances and the other Nonfiction instances.

catamorphism over Book type

We can rewrite our buggy if / then / else statement to one that is much more safe

The catamorphism for an Either (or Xor type)

We have just derived the catamorphism for a Book that can either be Fiction or Nonfiction. This can be generalized to account for a type that can either be one of two other types (e.g. type T1, type T2). A common datastructure to represent this is an Either type. (cyclops-react provides lazy & reactive implementations of Either for up to 5 choices and an eager version of the datastructure called Xor — eXclusive or). Much like how we can use Optional when a field is nullable, rather than consistently reimplement Eithers to represent inheritance hierarchies we can make use of the existing datastructure.

We can refactor our Book class to use Either instead

An to pattern match on the type of Book we can use the match method

The catamorphism for a List

When Lists are implemented in functionally, they are normally structured (recursively) in terms of a head and a tail

Head : first value

Tail : List containing a Head and a Tail

The catamorphism for a List would consist of a two parameter function (or BiFunction) that accepts both the first value of the list, and the tail (the rest of the list). We can easily implement this using the eXtended List type (ListX) in cyclops-react. ListX can wrap any standard j.u.List and adds a lot of useful fucntionality. Even though j.u.Lists are not (typically) implemented in terms of a Head and Tail, we can abstractly (or virtually) represent them as such and our simple catamorphism can still be applied.

With Scala pattern matching we can fold (or reduce) a List of Strings to a single String, by appending the head and recursively processing the tail.

In Java with our List catamorphism we can essentially do the same thing

Implementing your own catamorphisms

In this article we showed how simple it was to implement a catamorphism (or pattern matching) for one of the core Java 8 types — Optional. Then through a worked example, we implemented a very simple Case Class in Java with it’s own catamorphism. We showed how catamorphisms can simplify working with inheritance hierarchies in Java, by implementing the catamorphism for an Either type. Finally we implemented the functional catamorphism for a j.u.List even though it does not expose the simple recursive data structure of a head and a tail.

All of these catamorphisms were implemented in 3 lines of code or less, but they allowed us to pattern match on the important aspects of the structure of the types we created them for. You can do this in your own code base too.

Next time you find yourself wrangling with a gnarly if / then/ else sequence or case statement ask if this can be simplified somehow, almost certainly there is something about the structure of your Objects that can guide you in creating simple catamorphisms that will improve the robustness of your code.