Algebraic Data Structures

Algebraic data types are a fundamental part of modern functional programming languages, which allows the definition of complex composite types. They are algebraic, built upon two basic operations: products and sums.

Sum types encode alternative data. A sum type is either of value A or B, but not both. A product type, on the other hand, combines different values together, into a single unit.

 data Sum  = Sum1 a | Sum2 b;
 data Prod = Prod a b; 

These two operations can be further combined to form complex data structures, as we shall see in the examples below.

Boolean Values

 data Bool = False | True;

Peano Numbers

 data Num = Succ x | Zero; 

Tuples

 data Pair = Pair a b;
 data Trio = Trio a b c;
 data Quad = Quad a b c d;

Linked-lists

 data List = Cons a b | Nil;

Wheels

Wheels are a fixed-point of linked-lists, as in:

 wheel = Cons 1 (Cons 2 (Cons 3 wheel));
 wheel = Fix (\f -> Cons 1 (Cons 2 (Cons 3 f)));

Binary Trees

 data BTree1 = Fork a b | Leaf n;
 data BTree2 = Fork n a b | Leaf n; 
 data BTree3 = Fork n a b | Leaf; 

Maybe Monad

 data Maybe = Just x | Nothing;

Either Monad

 data Either = Left y | Right x;