The Algebra of Types

Static types can really aid in designing software, especially if your type system has good facilities for composing those types.

A case study

Let’s say we want to define a binary tree. Each node in a binary tree consists of an element and 0–2 children. Here’s how we could define a tree of integers in Haskell:

data Tree = Empty| Node Tree Int Tree

This syntax may not be familiar, so let’s break it down. We are defining a custom data type called Tree. The | (read “or”) indicates that there are two variants. We are recursively defining a Tree to be either Empty or Node.

Empty is the base case of our recursive definition, and represents an empty tree. It doesn't have any other data associated with it.

Node is the recursive part of our definition, and consists of Tree, an Int, and a Tree (the left subtree, current element, and right subtree, respectively).

We can create a tree with one element, a 3, as follows:

tree = Node Empty 3 Empty

Adding a 4 to the right looks like this:

tree' = Node Empty 3 (Node Empty 4 Empty)

Algebraic Data Types

Tree is an example of an Algebraic Data Type (ADT). ADTs can further be classified as sum and product types.

Product types

A product type is a combination of several values, or fields. Node above is an example of a product type. In this case, the fields are the left subtree, the current element, and the right subtree. (Think this and that, a boolean AND.)

Classes in an OO language are also examples of product types.

Sum types

A sum type is a set of multiple cases. Each of the cases may have some data associated with it. Tree above is a sum type, because it's either Empty or Node. (Think this or that, a boolean OR.)

Enums are the closest thing to sum types in an OO language. Enums can express variants, but can’t associate data with the different cases.

Types as building blocks

We can compose our types using sums and products, like building blocks, to create new types. This allows us to precisely and succinctly model our domain. Let’s look at another example to see how we might combine types together:

data Result = Success| Error String

This type allows us to model the result of a computation that might fail. In the case of an error, we will provide an error message. Result is a sum type (Success or Error), while Error String is a product type.

Conclusion

Not all static type systems are created equal. The Javas of the world provide product types in the form of classes, but don’t provide first-class support for sum types. This limits what you can express in your types.

To play around with ADTs, take a look at OCaml, F#, Haskell, Rust, Swift, or even TypeScript. It will change the way you approach modeling your domain.