(This is a post for CS320 Boston University.)

A type is a category of things having common characteristics. Putting it into our context, it is a classification identifying one of various types of data that usually determines [ref]

• the possible values for that type;
• the operations that can be done on values of that type;
• the meaning of the data;
• and the way values of that type can be stored.

Or, you can think of a type as a value space, a set of all possible values.

• integer type: `{... -2, -1, 0, 1, 2, ...}`
• boolean type: `{true, false}`
• char type: `{a, b, c, ...}`

### Primitive/Composite Types

Usually, we call them primitive type: `int`, `bool`, `string`, `float`, etc. They are building blocks for composite types. Composite types are types formed by combining other types.

### Algebraic Data Types

ADT is a kind of composite type. Depending on how the value space is determined by its composing types, we have product types and sum types. [ref]

#### Product Types

If P is a product type formed by A and B, then the value space of P is the cartisian product of the value space of A and B.

Suppose we have a pair of type `(bool, int)`, then it's value space should be `{..., (T -1), (F -1), (T 0), (F 0), (T 1), (F 1), ...}`. It is easily seen that this is simply a cartisian product of `{T, F}` and `{..., -1, 0, 1, ...}`.

These composing types are usually called fields. The above type contains two fields: the first is a bool field, the second is an int field. Fields may or may not have names/labels.

Examples of product types are: pairs, tuples, records, etc.

#### Sum Types

If S is a sum type formed by A and B, then the value space of S is the union of the value space of A and B.

For a sum type, each of its composing types is called a variant, and each variant is identified by a constructor. Constructors may or may not carry data of any type.

Suppose we have a `intlist` type:

``````datatype intlist =
| list_cons of (int, intlist)
| list_nil of ()
``````

The integer list type has two variants, identified by its two constructors: `list_cons` and `list_nil`.

• `list_cons` variant correspond to the set of all non-empty integer lists.
• `list_nil` variant correspond to the set of empty integer list.

And we also see, `list_cons` is carrying two pieces of data: an integer (representing the current/head list node), and an integer list (representing the rest of the list). But `list_nil` is carrying nothing.

### Defining Values of Some Type

For primitive types and product types, just write down the literal value of that type (which should be a member of the value space set).

``````val x = 3
val y = true
val z1 = (x, y)  // an unboxed/flat tuple
val z2 = '(x, y) // a boxed tuple

typedef point = @{x = double, y = double} // an unboxed record
val p = @{x = 0.0, y = 0.0 } : point

typedef student = `{name = string, id = int} // a boxed record``````

For sum types, we should instead use the constructor.

``````val l = list_nil ()
val ls = list_cons (1, list_nil ())

// 1 -> (2 -> (3 -> nil))
val lss = list_cons (1, list_cons (2, list_cons (3, list_nil ()))``````

After constructing sum type values, we can use pattern matching to retrieve the data we previously put into the constructor.

``````case+ lss of
| list_nil => println! ("Empty list!")
| list_cons (x, y) => println! (x)
``````

Because constructors can identify different variants of a sum type, it is perfect for pattern matching, which will help us interpret the ADT value, and reverse the process of constructing to get the data inside it. Here, `x` is matched with `1`, the head of the list. `y` is matched with `list_cons (2, list_cons (3, list_nil ())`, the rest of the list.

However, this is only a list of integers. It can't hold other types of data. We will solve this by polymorphic types later.