Pattern matching for the Java programmer: part 2
Leaky abstractions
The Java collections framework contains both Abstract Data Types like List and Set, and Data Structures like LinkedList, ArrayList, HashSet, and TreeSet. As programmers, we are advised to ensure the encapsulation of each object by using their well-defined interfaces without the visibility of their internals. In performance-sensitive scenarios, we need to think beyond the interface(like Set) and focus on implementations(like Tree Set and HashSet) when the implementations offer different asymptotic complexities.
The conundrum between encapsulation and performance is real, and thankfully it has been studied. Joel Spolsky in his essay The Law of Leaky Abstractions has listed a few scenarios where encapsulation has to be partially compromised for other desired qualities from software.
Composition
Programmers use two main techniques for assembling and composing functionality into more complex ones, inheritance, and object composition. Object composition is about combining objects within compound objects, and at the same time, ensuring the encapsulation of each object by using their well-defined interface without visibility of their internals.
Composition when accompanied by encapsulation facilitates the combiner objects to be more than the sum of their parts.
In this post, I will present a flavor of composition that forsakes encapsulation for in-lieu benefits.
Algebraic Types
Product Types
Advertising is pervasive across the internet, advertisements can contain parts which are text(title and body), video, or images. These parts need to undergo different operations such as render and review. These need access to the parts. Transparent access to parts is a mechanism that helps in the above-mentioned operations.
Ad is an example of a Product Type. Product Types are exactly the sum of their parts.
Java Beans technology is a manifestation of this style and introspection is a quality that drove this style.
Java Tuples is another library that is built on this style, where generics are exploited additionally.
Notation
The following notation is used to describe the relationship between the combiner and contained types
Ad ➝ (Title, Body, Image)
Sum Types
Consider payment options for an e-commerce site/app like Flipkart as shown below.
Customers are expected to employ exactly one of these options. Fraud detection, billing, and reversing are some of the payment-related operations. Each of these need to have exactly one of the parallel activities to handle each type of payment.
Payment is an example of a Sum Type. Sum types can be thought of as an extension of the concept of enumerations, where instead of a set of objects, here a set of types is provided.
Notation
Notation for sum types is shown below, vertical lines separate options.
Payment ➝ Credit Card | Cash | Debit Card | Net Banking
Sum Types and Product types together are termed Algebraic Types. They facilitate some interesting and powerful scenarios. The following section illustrates this.
Lists as an Algebraic Data Type
In this subsection, we will model List as an Algebraic Data Type
List<T> ➝ None<T> | (Node<T>, List<T>)
while JVM languages like Scala and Kotlin support these natively. This is not the case in Java at least in non-latest versions(There is support in Java 17).
Fortunately, we can still implement them. The following code snippet shows an implementation.
import java.util.function.BiFunction;
import java.util.function.Supplier;
public interface List<T> {
static <T> List<T> none(){
return new None<>();
}
static <T> List<T> concat(T head, List<T> tail){
return new LinkedList(head, tail);
}
<R> R match(Supplier<R> supplier, BiFunction<T, List<T>, R> function);
static class None<T> implements List<T> {
@Override
public <R> R match(Supplier<R> supplier, BiFunction<T, List<T>, R> function) {
return supplier.get();
}
}
static class Node<T> {
T t;
public Node(T t){
this.t = t;
}
}
static class LinkedList<T> implements List<T>{
Node<T> head;
List<T> tail;
public LinkedList(T head, List<T> tail){
this.head = new Node(head);
this.tail = tail;
}
@Override
public <R> R match(Supplier<R> supplier, BiFunction<T, List<T>, R> function) {
return function.apply(head.t, tail);
}
}
}Pattern Matching
pattern matching ➝ multiplexing + destructuring + delegation
Pattern matching in the context of Sum Types can be thought of as figuring out the option(multiplexing), passing control to it(delegation), opening it up, and operating on them(destructuring). While a lot seems to be happening, the following code snippets will illustrate the power of this mechanism.
public class SimpleFunctions {
//find the number of elements
<E> int count(List<E> list){
return list.match(() -> 0, (head, tail) -> 1 + count(tail));
}
// find the sum of elements
int sum(List<Integer> list){
return list.match(() -> 0, (head, tail) -> head + sum(tail));
}
//find if elements occurs in the list
<E> boolean contains(List<E> list, E element){
return list.match(() -> false, (head, tail) -> head.equals(element) || contains(tail, element));
}
}In the above snippets, how terse the code is. The terseness is an indicator of the high level of abstraction that the programmers can operate at.
The higher-order functions like fold, map, and flatmap can be easily implemented with pattern matching as shown below.
import java.util.function.BiFunction;
import java.util.function.Function;
public class ListFunctions {
<E> E fold(List<E> list, E zero, BiFunction<E, E, E> combiner){
return list.match(() -> zero, (head, tail) -> combiner.apply(head, fold(tail, zero, combiner)));
}
<E, F> List<F> map(List<E> list, Function<E, F> mapper){
return list.match(() -> List.none(), (head, tail) -> List.concat(mapper.apply(head), map(tail, mapper)));
}
<E> List<E> concatenate(List<E> list1, List<E>list2){
return list1.match(() -> list2, (head, tail) -> List.concat(head, concatenate(tail, list2)));
}
<E, F> List<F> flatmap(List<E> list, Function<E, List<F>> mapper){
return list.match(() -> List.none(), (head, tail) -> concatenate(mapper.apply(head), flatmap(tail, mapper)));
}
}Pattern matching has pervasive applications. Foundational structures like Trees, Set and Map are all candidates for pattern matching. This style can be applied at the application layer for domain modeling as in the case of payments.
