Think of an algebraic data type as a type composed of simpler types, where the allowable compositions operators are AND (written $\cdot$, 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\cdot X$, etc.
For example, the Haskell type
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 (1 - X) = 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 + 2X^2 + 5X^3 + 14X^4 + 42X^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.