## Introduction

Learning functional programming can be a rough experience. For those coming from procedural programming languages, a shift in paradigm is never easy and functional programming is known to employ some obscure mathematical constructs. In this wonderful journey, one is prone to find terms such as *algebraic data types*.

## What are algebraic data types and why should we care?

Simply put, algebraic data types are types made of other types. These are formed by composing previously existing types. Let us see two examples in our favourite programming language, Haskell!

### Two values at the same time

Everyone knows what a pair is. Intuitively, a pair allows us to hold two values.

```
data Pair = P String Int
-- P is a type constructor
-- P :: String -> Int -> Pair
= P "The answer to life" 42
pair1 = P "" 392
pair2
-- or more generally
data Pair a b = P a b
-- P :: a -> b -> Pair
pair1 :: Pair Int Int
= P 0 999
pair1
pair2 :: Pair Char ()
= P 'z' () pair2
```

We now have a type that allows to have values of multiple types, **at the same time**. In order to construct an instance of type *Pair a b* we need to give *P* a value of type *a* **and** a value of type *b*.

### You can’t have the cake and eat it too

In the previous example we have constructed a data type that combined two existing types, allowing them to exist at the same time. What about choice though? What if, I want to create a type that expresses a choice? I can have an *a* or a *b* but not both. In Haskell we can express it like this:

```
data Choice a b = I1 a | I2 b
-- I1 :: a -> Choice a b
-- I2 :: b -> Choice a b
a0 :: Choice Int b
= I1 10
a0
a1 :: Choice Int Int
= I1 11
a1
b :: Choice Int Char
= I2 'c' b
```

Any instance of type *Choice a b* will have a value of type *a* **or** a value of type *b*. Never both at the same type.

### Proper names and the algebra in algebraic

*Pair* and *Choice* are the quintessential examples of algebraic data types. In the Haskell world they are better known as *(,)* and *Either* respectively.

`(,)`

is a**product type**`Either`

is a**sum type**

Wait! Sum types? Product types? What?! Worry not, dear reader. These names make perfect sense, I promise you. It’s all about cardinalities! The cardinality of a type is the number of inhabitants the type has. Now that we know what cardinality means, let us analyze what we have already discussed.

#### Product types

A *Pair a b*, or *(a,b)*, allows us to combine values of different types. *Combine* is the keyword here.

```
-- For (Bool, Bool)
= (True, True)
a1 = (True, False)
a2 = (False, True)
a3 = (False, False)
a4
-- We have 4 different values of type `(Bool, Bool)`
-- Bool has two different values
```

A product type has as many inhabitants as the product of the cardinalities of its constructors.

#### Sum Types

*Either a b* allows us to have either a value of type *a* or a value of type *b*. Furthermore, the values are *tagged*.

```
e :: Either String a
= Left "error!"
e
-- notice that Left can be thought of as a tag
```

Sum types are dual to product types, meaning we can calculate their cardinality by *adding* the cardinalities of the types that compose them.

`data Smile = Happy | Sad | Excited`

*Either Bool Smile* has 5 inhabitants (2 + 3).

```
= Left True
a1 = Left False
a2 = Right Happy
a3 = Right Sad
a4 = Right Excited a5
```

### Some more examples

```
data Maybe a = Nothing | Just a
data Tree a = T | Node (Tree a) a (Tree a)
data List a = Nil | Cons a (List a)
```

Algebraic, sum types, product types, it all seems easy peasy now. They are just types composed of other types. This composition gives us tremendous flexibility.

Algebra | Types |
---|---|

a + b | Either a b |

a * b | (a, b) |

0 | data Void |

1 | data Unit = () |

As a quick side note, product types are often called *records* or *tuples* and sum types are often called *tagged unions* or *enumeration types*.

## Algebraic manipulation and isomorphisms

We have seen that each and every type has a cardinality associated to it. Once again, the cardinality of a type is the number of its inhabitants. **Intuitively**, if two types have the same cardinality, it is possible to define a one-to-one map between their inhabitants. This is an isomorphism. A pair of functions, from and to, witness an isomorphism in the following way:

```
to :: s -> t
from :: t -> s
-- to . from = id
-- from . to = id
```

For two types with cardinality `N`

, `N!`

different isomorphisms exist.

```
data Smile = Happy | Sad
data Bool = True | False
-- Isomorphism 1
toSmile1 :: Bool -> Smile
True = Happy
toSmile1 False = Sad
toSmile1
fromSmile1 :: Smile -> Bool
Happy = True
fromSmile1 Sad = False
fromSmile1
-- Isomorphism 2
toSmile2 :: Bool -> Smile
True = Sad
toSmile2 False = Happy
toSmile2
fromSmile2 :: Smile -> Bool
Happy = False
fromSmile2 Sad = True fromSmile2
```

With this in mind, we can change how we represent information, changing our types without losing information! Even better! Isomorphisms don’t appear out of thin air. They can be calculated.

```
data Choice a = I1 a | I2 a
-- a + a
```

Everyone knows that `a + a`

is equivalent to `2 * a`

. Shall we write this type?

```
type Choice a = (Bool, a)
-- 2 * a
```

```
data Choice a = I1 a | I2 a
fromChoice :: Choice a -> (Bool, a)
I1 a) = (True, a)
fromChoice (I2 a) = (False, a)
fromChoice (
toChoice :: (Bool, a) -> Choice a
True, a) = I1 a
toChoice (False, a) = I2 a toChoice (
```

I’ll bite the bullet and admit that these examples are a bit naive, but they showcase what can be done. Using simple algebraic laws we can calculate data representations and work with easier types.

## The end

What a long journey! I hope this post has cleared some doubts you might have had about algebraic data types. They are a powerful tool to have in your arsenal and I have no doubt you will bennefit from knowing about them. See you next time!