Algebraic Data Types in Kotlin

Photo by Spencer Watson on Unsplash

Following a post about representing ADTs in four different languages: Scala, Haskell, Rust and TypeScript, I’ve been thinking about how this would work in Kotlin world.

So, first we’ll need to define our data type. We’ll take Tree for two reasons:

• The original article uses trees in all examples, so we could compare apples to apples, or trees to trees
• It’s recursive, hence interesting to work with.

Kotlin sealed classes are a common way to implement ADTs.

First, let’s see the implementation, and then discuss in detail how it works:

So, our common interface is Tree. Since it’s a generic data structure, we define it with a type parameter: Tree<T>. We also use out variance annotation to indicate that this type is covariant. We’ll discuss why next.

Since all empty trees are the same, we declare Empty to be a singleton object, that extends Tree<Nothing>().

There’s a lot of confusion between Any, Nothing and <*> (also called star projection). Star projection simply wouldn’t work in this case. But you could define Empty as Tree<Any>(), and it would compile. In the next step we’ll see why this is a mistake.

Next let’s look at the Node class. It makes a lot of sense to define it as data class, since it will provide us with nice toString() method at the very least.

Note how we specify default values for left and right properties:

val left: Tree<T> = Empty

That’s where both covariance and Nothing come into play.

No matter what type our T is, Nothing is at the bottom of the class hierarchy, and so it’s safe to use.

This prints:

Node(value=42, left=Empty, right=Node(value=62, left=Empty, right=Empty))

Thanks to default parameters, we didn’t have to specify left and right for the leaf node, which is nice.

But printing is not that interesting in general.

How about we sum the values of all the nodes?

That’s the real power of ADTs in general, and Kotlin sealed classes in particular.

Since our classes are sealed, when expression is exhaustive and concise.

println(tree.sum()) // 104

Conclusions

• Kotlin provides good facilities for implementing ADTs
• Use object in case your variant doesn’t have state
• Prefer data class otherwise
• when expression is a power tool to work with ADTs in Kotlin

More reading:

Kotlin and Algebraic Data Types