Sonia Ayers

2022-07-03

What's the meaning of algebraic data type?
I'm reading a book about Haskell, a programming language, and I came across a construct defined "algebraic data type" that looks like
data WeekDay = Mon | Tue | Wed | Thu | Fri | Sat | SunThat simply declares what are the possible values for the type WeekDay.
My question is what is the meaning of algebraic data type (for a mathematician) and how that maps to the programming language construct?

Jayvion Mclaughlin

Think of an algebraic data type as a type composed of simpler types, where the allowable compositions operators are AND (written ⋅, often referred to as product types) and OR (written +, referred to as union types or sum types).
We also have the unit type 1 (representing a null type) and the basic type X (representing a type holding one piece of data - this could be of a primitive type, or another algebraic type).
We also tend to use 2X to mean X+X and ${X}^{2}$ to mean X⋅X, etc.
data List a = Nil | Cons a (List a)
tells you that the data type List a (a list of elements of type a) is either Nil, or it is the Cons of a basic type and another lists. Algebraically, we could write
$L=1+X\cdot L$
This isn't just pretty notation - it encodes useful information. We can rearrange to get
$L\cdot \left(1-X\right)=1$
and hence
$L=\frac{1}{1-X}=1+X+{X}^{2}+{X}^{3}+\cdot$
which tells us that a list is either empty (1), or it contains 1 element (X), or it contains 2 elements ${X}^{2}$, or it contains 3 elements, or...
For a more complicated example, consider the binary tree data type:
data Tree a = Nil | Branch a (Tree a) (Tree a)
Here a tree T is either nil, or it is a Branch consisting of a piece of data and two other trees. Algebraically
$T=1+X\cdot {T}^{2}$
which we can rearrange to give
$T=\frac{1}{2X}\left(1-\sqrt{1-4X}\right)=1+X+2{X}^{2}+5{X}^{3}+14{X}^{4}+42{X}^{5}+\cdots$
where I have chosen the negative square root so that the equation makes sense (i.e. so that there are no negative powers of X, which are meaningless in this theory).
This tells us that a binary tree can be nil (1), that there is one binary tree with one datum (i.e. the tree which is a branch containing two empty trees), that there are two binary trees with two datums (the second datum is either in the left or the right branch), that there are 5 trees containing three datums (you might like to draw them all) etc.

Do you have a similar question?