06 Algebraic Data Types

Let's play a game! Record or variant?

• A coin, which can be a penny, nickel, dime, or quarter
  • A variant, it let's us have a constructor for each coin
• A student, who has a name and ID number
  • A record, we know that we want two pieces of data for each data point. If we used a variant, we wouldn't be able to have both simultaneously
• A dessert, which has a sauce, a creamy component, and a crunchy component
  • A record, because it needs to have each of these three components, and it needs to have all three, not just one

The we need to pay attention to the conjunctions here. When we use "or," we generally want a variant, while when we use "and," we generally want a record or tuple.

We can call these one-of types and each-of types.

Records and Tuples are types of each-of types, while variants are types of one-of types.

Each of types are often also known as product types, and variants are often also known as sum types.

Variants are also known as tagged unions. We can model them like this:

type string_or_int = 
    | String of string
    | Int of int

$$(\texttt{strings}) \ \bigcup\ (\texttt{ints})$$

But it's more than this! We can have two of the same types

type blue_or_red_int = 
    | Blue of int
    | Red of int

$$(\color{blue}{\texttt{ints}}) \ \bigcup^+ \ (\color{pink}{\texttt{ints}})$$

This is known in mathematics as a tagged union.

---

These data types are called algebraic data types (because sums and products 😊)

The abbreviation is "ADT," which unfortunately has a name clash with "Abstract Data Types"