# Recitation 2: Tuples, records and datatypes

## Tuples

Every function in OCaml takes exactly one value and returns exactly one result.  For instance, our `squareRoot` function takes one float value and returns one float value.  The advantage of always taking one argument and returning one result is that the language is extremely uniform.   Later, we'll see that this buys us a lot when it comes to composing new functions out of old ones.

But it looks like we can write functions that take more than one argument!  For instance, we may write:

```let max1 (r1, r2) : float =
if r1 < r2 then r2 else r1
```
```max1 (3.1415, 2.718)
```
and it appears as if max1 takes two arguments.  In truth max1 takes one argument that is a 2-tuple (also known as an ordered pair.)

In general, an n-tuple is an ordered sequence of n values written in parenthesis and separated by commas as (expr, expr, ..., expr).  For instance, `(42, "hello", true)` is a 3-tuple that contains the integer `42` as its first component, the string `"hello"` as its second component, and the boolean value `true` as its third component.  Note that n can be 0, which gives the empty tuple `()`.  This is called "unit" in OCaml.

When you call a function in OCaml that takes more than one argument, you can pass it the arguments in a tuple.  For instance, when we write:

```max1 (3.1415, 2.718)
```
we're passing the 2-tuple `(3.1415, 2.718)` to the function `max1`.  We could just as well write:

```let args = (3.1415, 2.178)
```
which would then allow us to write
```max1 args (* evaluates to 3.1415 *)
```

The type of an n-tuple is written t1`*`...`*`tn.  For instance, the type of args above is `float * float`.  This notation is based on the Cartesian product in mathematics (i.e., the plane is R^2 = R * R).

Similarly, the 3-tuple `(42, "hello", true)` has type `int * string * bool`.  Notice that `max1` has type `(float * float) -> float`, indicating that it takes one argument (a 2-tuple of floats) and returns one result (a float).

Combining what we've seen so far, we can write a grammar for the basic types as follows:

t  ::=  `int`  |  `float`  |  `bool`  |  `string`  |  `char`  |   t1 `*` ... `*` tn  |  t1 `->` t2  |  `(`t`)`

There are a few tricky parts to this. The two most important are that `->` has lower precedence than `*`, so the types `(float * float) -> float` and `float * float -> float` are exactly the same type. The second is that `->` is right-associative, which means that

t1 `->` t2 `->` t3        and        t1 -> (t2 `->` t3)
are the same. This will come up when higher-order functions are discussed.

You can extract the first two components of a tuple by using the `fst` and `snd` operators, which retreive the first and second elements of a tuple, respectively.  However, there are no analogous functions for the other elements of a tuple.

So, for instance, we can rewrite the max function as follows:

```let max1 (pair : float * float) : float =
if (fst pair) < (snd pair) then (snd pair) else (fst pair)
```
and this is completely equivalent to the first definition.  This emphasizes that `max` really does take just one argument -- a pair of floating point numbers.  But of course, it's somewhat less readable than the first definition.  We can get closer to the first definition by declaring local values r1 and r2 and bind them to the appropriate components of the pair:

```let max1 (pair : float * float) : float =
let r1 = fst pair in
let r2 = snd pair in
if r1 < r2 then r2 else r1
```

### Pattern-matching tuples

This is a little better because we avoid re-computing the same expressions over and over again.  However, it's still not as succinct as our first definition of max.  This is because the first definition uses pattern matching to implicitly de-construct the 2-tuple and bind the components to variables `r1` and `r2`.  You can use pattern matching in a `let` declaration or in a function definition to deconstruct a tuple.  A tuple pattern is always of the form `(`x1:t1x2:t2,..., xn:tn`)`.  Pattern matching (either in a `let` or in the function declaration) is the encouraged method of extracting elements from tuples. It is often more efficient, and is almost always more concise and easier to read. For instance, here is yet another version of max that uses a pattern in a `let` declaration to deconstruct the pair:

```let max1 (pair : float * float) : float =
let (r1, r2) = pair in
if r1 < r2 then r2 else r1
```

In the example above, the `let` declaration matches the pair against the tuple-pattern `(r1, r2)`.   This binds `r1` to the first component `(fst pair)` of the pair and `r2` to the second component `(snd pair)`.  A similar thing happens when you write a function using a tuple-pattern as in the original definition of max:

```let max1 (r1, r2) : float =
if r1 < r2 then r2 else r1
```

Here, when we call max with the pair `(3.1415, 2.718)`, the tuple is matched against the pattern `(r1, r2)` and `r1` is bound to `3.1415` and `r2` to `2.718`.  As we'll see later on, OCaml uses pattern matching in a number of places to simplify expressions.

Suppose we wanted to extract both the minimum and the maximum of two numbers in a single function. With tuples, this is easy: we just return a tuple containing both results. Using a let, we can extract both results into separate variables conveniently, too:

```let minmax (a, b) : float * float =
if a < b then (a, b) else (b, a)
```
```let (mn, mx) = minmax (2.0, 1.0)
```

This binds `mn` to `1.0` and `mx` to `2.0`. The type of `minmax` is `(float * float) -> (float * float)`, which we can write without the parentheses because `*` has a higher precedence than `->` when writing type expressions.

In summary:

• every function in OCaml takes one argument and returns one result.
• the value of the expression `(`e1`,` ...`,` en`)` is an n-tuple.
• tuple types look like  t1 `*` ... `*` tn
• the functions `fst` and `snd` extract the first and second components of a 2-tuple
• `let``(`x1:t1x2:t2,..., xn:tn`)`= e matches the value of the expression e, which must be an n-tuple, against the tuple-pattern `(`x1:t1x2:t2,..., xn:tn`)` and binds the identifiers in the pattern to the appropriate components of the tuple.
• `let` y`(`x1:t1x2:t2,..., xn:tn`)`= e is a declaration of a function y that takes an n-tuple as an argument and matches that tuple against the tuple-pattern `(`x1:t1x2:t2,..., xn:tn`)`, then evaluates e with those bindings.

## Records

Records are similar to tuples in that they are data structures for holding multiple values.  However, they are different from tuples in that they carry an unordered collection of labeled values.  Record expressions are of the form `{`x`1=`e1`;`...`;`xn`=`en`}` where the identifiers x are labels.  Before making a record, however, you must give its type a name, using the `type` keyword.  To declare a record type, the type must be enclosed in braces and each field must be given a name and a type of its own. For example, the following declares an `account` type:

```type account = {first:string; last:string; age:int; balance:float}
```

Once you have declared the type, you may create records of that type. For example, given the declaration of the `account` type, the expression

```{first="John"; last="Doe"; age=150; balance=0.12}
```
is a record with four fields named `first`, `last`, `age`, and `balance`.  You can extract a field from a record by using `exp.id` where `exp` is the record and `id` is the field that you want to extract.  For instance, applying `.age` to the record above yields 150, whereas applying `.balance` yields 0.12.

When creating a record, it does not matter in what order you give the fields.  So the record

```{balance=0.12; age=150; first="John"; last="Doe"}
```
is equivalent to the example above.  When you type in one of these records to the OCaml top-level, it sorts the fields into a canonical order, based on the order in the declaration of the type:

```# let pers = { last = "Doe";
age = 150; balance = 0.12;  first = "John" };;
val pers : account = {first = "John"; last = "Doe";
age = 150; balance = 0.12}
```

The type of a record is written as `{`x1:t1x2:t2; ... ; xn:tn`}`

Just as you can use pattern-matching to extract the components of a tuple, you can use pattern matching to extract the fields of a record.  For instance, you can write:

```let {first=first; last=last; age=age; balance=balance} = pers
```
and OCaml responds with:
```val first : string = "John"
val last : string = "Doe"
val age : int = 150
val balance : float = 0.12
```
thereby binding the identifiers `first`, `last`, `age`, and `balance` to the respective components of the record.  You can also write functions where the argument is a record using a record pattern. For example:

```let full_name {first=first; last=last; age=age; balance=balance} : string =
first ^ " " ^ last (* ^ is the string concatenation operator *)
```

Calling `full_name` and passing it the record `pers` yields ``` "John Doe"``` as an answer.

It turns out that we can think of tuples as shorthand for records.  In particular, the tuple expression `(3.14, "Greg", true)` is like the record expression `{1=3.14; 2="Greg"; 3=true}`.  So in some sense, tuples are just syntactic sugar for records.

In summary:

• you must declare record types using `type` before making them
• record expressions are of the form `{`x1 `=` e1`;` x2 ` =` e2`;` ...`;` xn `=` en`}`.
• record types are of the form `{`x1:t1x2:t2; ... ; xn:tn`}`.
• you can extract a field from a record by writing e`.`x, where x is the name of the field.
• you can pattern match records using a pattern of the form `{`x1=id1x2=id2; ... ; xn=idn`}`.

We'll cover more kinds of types (datatypes) and more pattern matching constructs next week.

## Simple Datatypes and Match Expressions

Datatypes are used for two basic purposes which we'll describe by example.  The first example of a datatype declaration is as follows:

```type mybool = Mytrue | Myfalse
```

This definition declares a new type (`mybool`) and two constructors (`Mytrue` and `Myfalse`) for creating values of type `mybool`.  In other words, after entering this definition into OCaml, we can use `Mytrue` and `Myfalse` as values of type `mybool`.  Indeed, these are the only values of type `mybool`.  So one purpose of datatypes is to introduce new types into the language and to introduce ways of creating values of this new type.  In fact, the builtin `bool` type is simply defined as:

```type bool = true | false
```

Notice that a datatype definition is a lot like a BNF grammar.  For instance, we can think of bool as consisting of `true` or `false`.  We'll use this built-in grammar fracility in OCaml to good effect when we start building implementations of languages.

Side note: the logical operators for conjunction and disjunction are as follows:

exp   ::=   ...   |   e1 && e2   |   e1 | | e2

Note that `and` is not for logical conjunction, although it is a keyword.  These appear to be like binary operators; however, they are different from infix functions as all the other binary operators evaluate both expressions.  These two logical constructs have a special capability called short-circuiting.  If the result of the logical formula can be determined by evaluating the left-hand expression, the right-hand expression will remain unevaluated.

Another example of a datatype declaration is as follows:

```type day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
```

This declaration defines a new type (`day`) and seven new constructors for that type (`Sun``Sat`).  So, for example, we can write a function which maps a number to a day of the week:

```let int_to_day (i : int) : day =
if i mod 7 = 0 then Sun else
if i mod 7 = 1 then Mon else
if i mod 7 = 2 then Tue else
if i mod 7 = 3 then Wed else
if i mod 7 = 4 then Thu else
if i mod 7 = 5 then Fri else Sat
```

This sequence of `if` expressions where we test the value `i` is rather tedious.  A more concise way to write this is to use a `match` expression:

```let int_to_day (i : int) : day =
match i mod 7 with
0 -> Sun
| 1 -> Mon
| 2 -> Tue
| 3 -> Wed
| 4 -> Thu
| 5 -> Fri
| _ -> Sat
```

The `match` expression is similar to the `switch` statement in languages such as Java or C.  In the example above, we perform a case on the value of (`i mod 7`) and match it against a set of number patterns (i.e., 0, 1, 2, etc.)   The last pattern is a wildcard and matches any value.  In Java, we would write the above as something like:

```switch (i % 7) {
case 0: return Sun;
case 1: return Mon;
case 2: return Tue;
case 3: return Wed;
case 4: return Thu;
case 5: return Fri;
default: return Sat;
}
```

So much for mapping integers to days.  How about mapping days to integer?

```let day_to_int (d : day) : int =
match d with
Sun -> 0
| Mon -> 1
| Tue -> 2
| Wed -> 3
| Thu -> 4
| Fri -> 5
| Sat -> 6
```

With `match` expressions, we technically don't need an `if` expression form.  In particular, an expression of the form `if` exp1 `then` exp2 `else` exp3 is equivalent to:

```match exp1 with
true -> exp2
| false -> exp3
```

In fact it turns out that with the general form of datatypes and case expressions, we can encode a lot of things that appear to be built in to the language.  This is a good thing because it simplifies the number of special forms that we have to reason about.

In summary:

• `type` id = id1 | id2 | id3 | ... | idn  declares a new type (id1) with n data constructors (id1 id2 id3 ... idn).
• `match` exp `with` pat1 -> exp1 | pat2 -> exp2 | ... | patn -> expn evaluates exp and then successively matches it against the patterns.  That is, the first pattern (pat1) is tried first and if matching succeeds, then we evaluate the corresponding expression (exp1).  If matching fails, then we proceed to the next pattern pat2 and so on.
• So far, patterns can be made up of integers (e.g., 12, ~4), identifiers that are variables (e.g., `x`), tuple patterns, record patterns, or identifiers that are data constructors (e.g., `Sun`, `Mon`, `true`, etc.)
• The `if`-expression is a syntactic sugar for a `match`-expression.

## Algebraic Datatypes and Even More Pattern Matching:

A record (or tuple) is logically like an "and".  For instance, a tuple of type `int * float * string` is an object that contains an `int` and a `float` and a `string`.  Datatypes, in the most general form, are used for defining "or" types -- when something needs to be one type or another.  In particular, suppose we want to define a new type "number" that includes elements of type either `int` or `float`.  This can be accomplished in OCaml by the following datatype definition:

```type num = Int_num of int | Real_num of float
```

This declaration gives us a new type (`num`) and two constructors `Int_num` and `Real_num`.  The `Int_num` constructor takes an `int` as an argument and returns a `num`, while the `Real_num` constructor takes a `float` as an argument and returns a `num`.  In this fashion, we can create a type that is the (disjoint) union of two other types.

But how do we use a value of type `num`?  We can't apply an operation such as + to it, because + is only defined for `int`.  In order to use a value of type `num`, we have to use pattern matching to deconstruct it.  For example, the following function computes the maximum of two nums:

```let num_to_float (n : num) : float =
match n with
Int_num i -> float_of_int i
| Real_num r -> r
```
```let max1 (n1, n2) : num =
let r1 : float = num_to_float n1 in
let r2 : float = num_to_float n2 in
if r1 >= r2 then Real_num r1 else Real_num r2
```

The strategy is simple:  convert the numbers to floats and then compare the two floating point numbers, returning the larger of the two.  In order to make the return value a `num` (as opposed to a `float`), we have to put the result in a `Real_num` constructor.  We could just have well written this as:

```let max2 (n1, n2) : num =
let r1 : float = num_to_float n1 in
let r2 : float = num_to_float n2 in
Real_num (if r1 >= r2 then r1 else r2)
```

Here, we've wrapped the whole `if`-expression with the `Real_num` constructor.  This is one advantage of treating `if` as an expression as opposed to a statement.

Notice that in the function `num_to_float`, we use a `match`-expression to determine whether the number n is an integer or float.  The pattern `Int_num i` matches n if and only if n was created using the `Int_num` data constructor, and `Real_num r` matches n if and only if it was created with the `Real_num` data constructor.  Also, notice that in the `Int_num i` case, we have bound the underlying integer carried by the data constructor to the variable `i` and that this is used in the expression `float_of_int i`.  Similarly, the `Real_num r` pattern extracts the underlying float value carried by the data constructor and binds it to `r`.

So, for instance, calling `num_to_float (Int_num 3)` matches the first pattern, binds `i` to 3, and then returns `float_of_int i` = `float_of_int 3` = `3.0`.  Calling `num_to_float (Real_num 4.5)` fails to match the first pattern, succeeds in matching the second pattern, binds the `r` to 4.5, and then returns `r` = `4.5`.

Here is an alternative definition of max on numbers.

```let rec max2 (n1, n2) : num =
match (n1, n2) with
(Real_num r1, Real_num r2) -> Real_num (max r1 r2)
| (Int_num i1, Int_num i2) -> Int_num (max i1 i2)
| (_, Int_num i2) -> max2 (n1, Real_num (float_of_int i2))
| (Int_num i1, _) -> max2 (n2, Real_num (float_of_int i1))
```

Notice that that `match` expression in `max2` matches a tuple of the numbers `n1` and `n2`.  Thus, all of the patterns in the case expressions are of the tuple form.  For example, the pattern ```(Real_num r1, Real_num r2)``` matches if and only if both the numbers are floats.

In the third and fourth patterns, we've used a "wildcard" (or default) pattern.  For instance, the third pattern `(_, Int_num i2)` matches iff the first number is anything, but the second is an integer.  In this case, we simply convert the integer to a float and then call ourselves recursively.  Similarly, the fourth pattern `(Int_num i1, _)` the first number is an integer and the second number is anything.  In this case, we convert the first number to a float and call ourselves recursively.

Now suppose we call `max2` with two integers `max2 (Int_num 3, Int_num 4)`.  It appears as if this matches any of the last three cases, so which one do we select? The answer is that we try the matches in order.  So the second pattern will succeed and the other patterns won't even be tried.

Another question is, how do we know if there is a case for every situation?  For instance, suppose we accidentally wrote:

```let rec max3 (n1, n2) : num =
match (n1, n2) with
(Int_num i1, Int_num i2) -> Int_num (max i1 i2)
| (_, Int_num i2) -> max3 (n1, Real_num (float_of_int i2))
| (Int_num i1, _) -> max3 (n2, Real_num (float_of_int i1))
```

Now there is no case for when `n1` and `n2` are both floats.  If you type this in to OCaml, then it will complain that the pattern match is not exhaustive.  This is wonderful because it tells you your code might fail since you forgot a case!  In general, we will not accept code that has a match not exhaustive warning.  That is, you must make sure you never turn in code that doesn't cover all of the cases.

What happens if we put in too many cases?  For instance, suppose we wrote:

```let rec max2 (n1, n2) : num =
match(n1, n2) with
(Real_num r1, Real_num r2) -> Real_num(max r1 r2)
| (Int_num i1, Int_num i2) -> Int_num (max i1 i2)
| (_, Int_num i2) -> max2 (n1, Real_num (float_of_int i2))
| (Int_num i1, _) -> max2 (n2, Real_num (float_of_int i1))
| (_, _) -> n1
```

Then OCaml complains that the last match case is unused (i.e., it will never be reached).  Again, this is wonderful because it tells us there's some useless code that we should either trim away, or reexamine to see why it will never be executed.  Again, we will not accept code that has redundant patterns.

So how can the OCaml type-checker determine that a pattern match is exhaustive and that there are no dead cases?  The reason is that patterns can only test a finite number of things (there are no loops in patterns), the tests are fairly simple (e.g., is this a `Real_num` or an `Int_num`?) and the set of datatype constructors for a given type is closed.  That is, after defining a datatype, we can't simply add new data constructors to it.  Note that if we could, then every pattern match would be potentially inexhaustive.

At first, this seems to be a shortcoming of the language.  Adding new constructors is something that happens all the time, just as adding new subclasses happens all the time in Java programs.  The difference in OCaml is that, if you add a new data constructor to a datatype declaration, then the compiler will tell you where you need to examine or change your code through "match inexhaustive" errors.  This makes pattern matching an invaluable tool for maintaining and evolving programs.

So sometimes, by limiting a programming language we gain some power.  In the case of the pattern-matching sub-language of OCaml, the designers have restricted the set of tests that can be performed so that the compiler can automatically tell you where you need to look at your code to get it in sync with your definitions.