I am a big fan of Algebraic Data Types. They allow us to declaratively specify data model grammar. Many modern statically typed languages deliver this functionality out of the box, allowing for writing very expressive code. Since I primarily work with Java I have tried to use ADTs in Java on a number of occasions. That has not been a pleasant experience. Java simply does not provide proper tools. Last time I tried, it was with Java 11. Now that we are at Java 15 I have decided to give another go, using new features.

One of the basic data structures that we work with are Lists. When learning a functional language they are usually the first hurdle that takes a while to get your head around. In Haskell a List is pretty much defined as:

data List a = Empty | Cons a (List a)

This means that a List is either Empty (no elements) or has an element and a pointer to the next “object”. In short this is the definition of a Linked List. Pretty neat, right? To not come across as some Haskell snob the same can be done in Typescript:

type List<T> = null | {value: T, next: List<T>}

I tried to recreate that in Java 15 and came up with this:

public sealed interface LinkedList<T> permits LinkedList.Nil, LinkedList.Cons {
    record Nil<T>() implements LinkedList<T> {}
    record Cons<T>(T value, LinkedList<T> next) implements LinkedList<T> {}
}

We have few new things done here that were not possible before.

First we have sealed classes (https://openjdk.java.net/jeps/360). Those are classes/interfaces that strictly define what classes can inherit from them. This means that when we check the type of the object we can do it exhaustively. One of the major critiques of using instanceof is the fact that we never truly know what implementations we can encounter. Until now. This allows us to safely deliver more logic through the type system, allowing the compiler to verify it for us.

Second are records (https://openjdk.java.net/jeps/384). Those allow us to declare immutable data models with far less boilerplate. Would be great if we didn’t need those curly brackets at the end :).

So this is the definition of the LinkedList using type system in Java 15. Lets see it in action:

LinkedList<String> emptyList = new LinkedList.Nil<>();
System.out.println(emptyList);
LinkedList<String> oneElementList = new LinkedList.Cons<>("Test", new LinkedList.Nil<>());
System.out.println(oneElementList);

Let’s try to build a bigger list. To do that we need a util method:

static <T> LinkedList<T> addElement(LinkedList<T> list, T element) {
    if (list instanceof Nil<T>) {
        return new Cons<>(element, new Nil<>());
    } else if (list instanceof Cons<T> cons) {
        return new Cons<>(cons.value, addElement(cons.next, element));
    } else {
        throw new IllegalArgumentException("Unknown type");
    }
}

Here we yet again take advantage of a new Java feature: instanceof pattern matching (https://openjdk.java.net/jeps/375). This allows us to skip the type casting after the instanceof check, making for a more readable code. Actually, once more work is done in this area and we get the planned switch expression for instanceof, will end up with something akin to:

static <T> LinkedList<T> addElement(LinkedList<T> list, T element) {
    return switch (list) {
        case Nil<T> nil -> new Cons<>(element, new Nil<>());
        case Cons<T> cons -> new Cons<>(cons.value, addElement(cons.next, element));
    }
}

Which will finally be quite pleasant to the eye. We can use this code as simply as:

LinkedList<Integer> list = new LinkedList.Nil<>();
for (int i = 0; i < 10; i++) {
    list = addElement(list, i);
}

I have added several more functions to the solution and the complete code can be found here.

Conclusion

So there it is. An immutable LinkedList written using the type system. There is still space for improvement but I feel like Java is on the right track. Although those features are still in preview I have high hopes that when we reach the next LTS (Java 17?) we will be able to truly take advantage of ADT techniques. Of course Java is playing a sort of catch up to other JVM languages like Kotlin and Scala but I hope that their implementation will be better since Java can play with JVM as it sees fit. Next time someone asks you to implement a Linked List in an interview, you can just use this :P.