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 . 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. Java 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 that wikipedia In functional , provide generalizations of folds of lists to arbitrary algebraic data types, which can be described as initial algebras programming catamorphisms 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 on Kristopher Roller 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 We make Book an abstract class, as we now have two concrete types (Fiction and Nonfiction instead) We define the two sub-types (Fiction and Nonfiction) 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 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. either 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 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. Either 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.