What are algebraic data types?

Sometimes is difficult to understand some concepts because the terms used to describe them are too mathematical and nobody wants to spend hours looking for a definition that can help you to move on and continue learning. Well, I am going to try my best to explain what are algebraic data types in an easy way.

Definition #

In computer programming, especially functional programming and type theory, an algebraic data type (ADT) is a kind of composite type, i.e., a type formed by combining other types. Two common classes of algebraic types are product types (i.e., tuples and records) and sum types (i.e., tagged or disjoint unions, coproduct types or variant types).

Wikipedia

Yeah I know, is a bit hard to process if you come from an object-oriented language or you are not too close to math definitions but believe me, is not as difficult as it looks, let’s break it down.

When we talk about a Kind of composite type we are talking about (redundantly) a type that is formed by other types. So we could say Animal = Dog or Cat or Eagle because Animal is formed by a Dog or a Cat or and Eagle (we have more types but for the sake of the example is enough).

Now that we have a better shape, let’s take a look to the next definition “two common classes of adts are product and sum types” so let’s break it down a bit more.

Sums #

This is what we already have seen and I am going to use some example code in Typescript to make it more familiar to everybody but first, let’s define something important:

type Dog = 'Dog' 
type Cat = 'Cat' 

Sum(Cat, Doc) = Cat or Dog

The best way to understand this is by using the Boolean type:

Boolean = true or false //which is equal to
Sum(true, false) = true or false 

Now let’s make the same example but in typescript:

 type Animal = Cat | Dog 

The pipe (|) symbol is used in union types (a union type describes a value that can be one of several types), an Animal can be Cat or a Dog, which follows the rule of our Sum type.

We can also say that sum type cardinality (the number of values it is composed) is the algebraic sum of the cardinalities of its types .

Animal cardinality = Dog cardinality (1) + Cat
cardinality (1) = 2 

Products #

As we have seen, a sum type is composed by “or” operations, in products we change that for “and” operations, let’s take a closer look.

Let’s imagine our same example, type Animal but now let’s create another type called AnimaTuple to represent the product type. In case you don’t know what a tuple is, a tuple is an ordered list with a finite number of elements that can hold values of different type .

type AnimalTuple = [Animal, Animal]

const animalTuple1 = ['Dog', 'Cat'] 
const animalTuple2 = ['Cat', 'Dog'] 
const animalTuple3 = ['Cat', 'Cat'] 
const animalTuple4 = ['Dog', 'Dog']

Now we have a new type called AnimalTuple that holds two elements of type Animal, and guess what… the type Animal can be a Dog “or” a Cat, so the possible options that we have for AnimalTuple are 4.

We can say that product type cardinality (the number of values it is composed) is the algebraic product of the cardinalities of its types .

AnimalTuple cardinality = Animal cardinality (2) * Animal cardinality (2) = 4

Conclusions #

1. Sum types are operations with “or” while product types are operations with “and”
2. Sum type cardinaly is the sum of its types cardinality
3. Product type cardinaly is the product of its types cardinality
4. Sum types and product types are combined so an Algebraic data type is a composite type different types, like sum, product or both recursively.

Useful complementary information #

• Practicing Typescript: Generalized Algebraic Data Types
• Algebraic Data Types
• Boolean Blindness