## 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`. <image style="float: right;" src="https://upload.wikimedia.org/wikipedia/commons/thumb/1/1a/Cartesian_coordinates_2D.svg/300px-Cartesian_coordinates_2D.svg.png" alt="Quadrant 1: x, and y both positive. Quadrant 2: x negative, y positive. Quadrant 3: both x and y negative. Quadrant 4: x positive, y negative." /> **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 (\*) <image style="float: right;" src="expr.png" width="300px" alt="Expression tree: * at the root, + in the left branch, + in the right branch, - as right subchild of right branch" /> 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)) ```