## Types and expressions
**Exercise:** Give a type definition and a value of that type for each of the
following:
* A set of sets, where the type of elements can by anything, and where sets
are represented by lists.
* A list of triples, the first two components of which have the same type,
and the third component of which is of some possibly different type.
* The suit of a card deck.
* A type whose values are "things", where a "thing" is either an integer or
a list of "things".
* A type whose values are pairs whose components can be of any
type, as long as they
are of the same type.
## Binary trees
Variants are a very natural way to represent many data structures, especially
tree-like data structures. In this section, we'll use them to build binary
search trees.
**Exercise**: a binary search tree is made up of nodes. Each node is either
a data node, which contains a key, a value, a left child, and a right child,
or it is a leaf node, which contains nothing at all. Complete the following
type definition:
```
type ('k, 'v) bstree = ...
```
A binary search tree should satisfy the property that for any
data node `n`, all of the values in the left subtree of `n` have keys that are
less than `n`, and all of the values in the right subtree of `n`
have keys that are greater than `n` (we do not allow duplicate values).
**Exercise**: Write a function `lookup : 'k -> ('k, 'v) bstree -> 'v`
that returns the value associated with the given key, and fails if the key
is not in the tree.
**Exercise**: Write a function `insert : 'k -> 'v -> ('k, 'v) bstree -> ('k, 'v) bstree`
that adds a new key-value mapping to the given binary search tree.
## More on patterns
So far we have seen many different kinds of patterns. We can match tuples:
```
match (3,5) with
| x, y -> x + y
```
We can match lists:
```
match [1;2;3] with
| [] -> "empty"
| h::tl -> "nonempty"
```
We can match options:
```
match Some 3110 with
| Some x -> x
| None -> 0
```
Here is the general rule: A pattern is any (non-function) value with some of
the subexpressions replaced by variables (note that `_` acts just like a
variable, except you can't use its value in the body of the match). For
example, the following patterns all match the expression `[Some 3110; None]`:
- `h :: tl`
- `(Some x)::tl`
- `[Some 3110; None]`
- `[Some x; _]`
- `h1::h2::tl`
- `h1::h2::[]`
**Exercise**: for each pattern in this list, give a value of type
`int option list` that does *not* match the pattern.
You can often simplify complicated match statements considerably by choosing
good patterns.
**Exercise**: Complete the following function, which should return true if the
length of the argument is odd:
```
let rec length_is_odd l = match l with
...
```
Do not use `if`.
**Exercise**: Complete `quadrant` function below, which should return the quadrant
of the given `x, y` vector, according to the diagram on the right (borrowed from [Wikipedia](https://en.wikipedia.org/wiki/File:Cartesian_coordinates_2D.svg)):
```
let quadrant (x,y) = match ... with
| ... -> 1
| ... -> 2
| ... -> 3
| ... -> 4
```
Hint: match a pair. Output on axes or the origin is unspecified.
**Exercise**: Write a function `is_bst : ('k,'v) bstree -> bool` that returns
`true` if the given tree satisfies the binary search tree property. You may
find it helpful to write a recursive helper function that takes a tree and
either gives you (i) the minimum and maximum value in the tree, or (ii) tells
you that the tree is empty, or (iii) tells you that the tree is not well formed.
What would be a good return type for that helper?
## Polymorphic variants
Thus far, whenever you've wanted to define a variant type, you have had to give
it a name:
```
type day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
type shape =
| Point of point
| Circle of point * float (* center and radius *)
| Rect of point * point (* lower-left and upper-right corners *)
type 'a mylist = Nil | Cons of 'a * 'a mylist
```
Here you've introduced the names `day`, `shape`, and `'a mylist`.
Occasionally, you only need a type for a single function, and creating a new
type name for just that function can create clutter. OCaml supports this using
so-called "polymorphic variants" (a better name might be "anonymous variants",
but "polymorphic" is the standard terminology).
Polymorphic variants are just like plain-old variants, except:
1. You don't have declare them before using them
2. They don't have names
3. The constructors start with `` ` `` (this is a back tick, typically found on the
same key as the `~` character, near the escape key).
For example, you may wish to write a function that can either return an integer
answer or "infinity". Without using polymorphic variants, you might write
something like the following:
```
type my_function_result = Finite of int | Infinity
let my_function x = match x with
| 0 -> Infinity
| 1 -> Finite 1
| n -> Finite (-n)
```
The downside to using this kind of definition is that the type of `my_function`
is `int -> my_function_result`, which isn't very edifying. Instead, you could
use polymorphic variants:
```
let my_function x = match x with
| 0 -> `Infinity
| 1 -> `Finite 1
| n -> `Finite (-n)
```
With this definition, the type of `my_function` is
```
val my_function : int -> [> `Finite of int | `Infinity ]
```
This makes clear that `my_function` either returns `` `Finite n`` or
`` `Infinity``.
**Exercise:** alter your implementation of `is_bst` to use polymorphic variants.
The `>` sign in the type ``[> `Finite of int | `Infinity ]`` means that the type
can be used in any code that can handle *at least* the constructors `` `Finite``
and `` `Infinity``, but maybe more. For example, we could write
```
match my_function 3 with
| `NegInfinity -> "negative infinity"
| `Finite n -> "finite!"
| `Infinity -> "infinite"
```
We will not require extensive use of polymorphic variants in this course, but if
you are curious, [RWO chapter 6](https://realworldocaml.org/v1/en/html/variants.html#polymorphic-variants)
covers them in much more detail.
## Expressions (\*)
Variants are also an excellent way to represent arithmetic expressions. An
expression like `3 + 5` can be thought of as a node of a tree, with `3` and `5`
as the two children. More complicated expressions like `(3 + 5) * (7 - 2)` can
be represented by more complicated trees, like the one on the right.
This tree might be represented by the following variant:
```
Times (Plus (Int 3, Int 5), Plus (Int 7, Neg (Int 2)))
```
**Exercise:** Write a variant type `expr` suitable for representing arithmetic
expressions with integer constants.
**Exercise:** Write a function `eval : expr -> int` that computes the value of
an arithmetic expression.
**Exercise:** Write a function `normalize : expr -> expr` that replaces all
negative constants with `Neg` applied to a positive constant. For example,
```
utop# normalize (Plus (Int -3, Int 2));;
val - : expr = Plus (Neg (Int 3), Int 2)
```
**Exercise:** Write a function `remove_negs : expr -> expr` that removes *all*
`Neg` constructors by pushing them all the way down to the constants. For
example:
```
utop# remove_negs (Neg (Plus (Neg (Int 3), Neg (Times (Neg (Int 1), Int 4)))));;
val - : expr = Plus (Int 3, Times (Int -1, Int 4))
```