## Types and Expressions
Assume the following type definition:
```OCaml
type student = { first_name : string ; last_name : string ; gpa : float }
```
Give OCaml expressions that have the following types:
* `int * char -> int`
* `int * char list -> (int * char) list`
* `student`
* `student -> string * string`
* `string -> string -> float -> student`
## Options
In this section, we'll look at a new built-in OCaml data type.
Suppose you want to write a function that *usually* returns a value of type
`t`, but *sometimes* returns nothing. For example, you might want to define a
function `list_max` that returns the maximum value in a list, but there's not a
sensible thing to return on an empty list:
```
let rec list_max l = match l with
| [] -> ???
| hd::tl -> max hd (list_max tl)
```
There are a few possibilities to consider:
- Return `min_int`. But then `list_max` will only work for ints.
- Raise an exception. In OCaml, the expression `failwith "message"` raises
an exception. It has type `'a`, which means you can use it any place you
would use any expression.
**Exercise**: write a version of `list_max` that fails if the list is empty.
- In Java, you might return `null`. OCaml does not have a `null` value.
(Which is actually a good thing: `NullPointerException` is your
favorite thing to debug, right?)
In addition to those possibilities, OCaml provides something even better
called "options."
In OCaml, `t option` is a type for every type `t`, much like `t list` is a type
for every type `t`. Values of type `t option` might contain a value of type
`t`, or they might contain nothing.
### Syntax and semantics of options
- `t option` is a type for every type `t`.
- `None` is a value of type `'a option` (much like `[]` has type `'a list`).
- `Some e` is an expression of type `t option` if `e : t`.
If `e ==> v` then `Some e ==> Some v`
**Exercise**: write a function `safe_hd : 'a list -> 'a option` that returns
`Some x` if the head of the input list is `x`, and `None` if the input list is
empty.
**Exercise**: write a function `safe_tl : 'a list -> 'a list option` that returns
the tail of the list, or `None` if the list is empty.
You can access the contents of an option using pattern matching:
```
match e with
| Some x -> ...
| None -> ...
```
**Exercise**: write a function `list_max : 'a list -> 'a option` that returns
the maximum element of a list, or `None` if the list is empty.
Using options is usually considered better style than raising exceptions,
because it forces the caller to pattern match on the result.
That pattern match reminds them to do something sensible in the `None` case.
## Pokémon
* Define the type `pokemon` to be a record with fields `name` (a string),
`hp` (an integer), and `ptype` (as defined in [lecture](lec.pdf#page=29)).
* Create a record named `charizard` of type `pokemon` that represents
a Pokémon with 78 HP and Fire type.
* Create a record named `metapod` of type `pokemon` that represents
a Pokémon with 50 HP and Normal type.
* Write a function `max_hp : pokemon list -> pokemon option` that, given a list of
`pokemon`, finds the Pokémon with the highest HP.
* Write a function `avg_hp : pokemon list -> float option` that, given a list of
`pokemon`, finds the average HP of Pokémon in the list. If the list is
empty, it should return `None`.
## Dates
Define a *date-like triple* to be a
value of type `int*int*int`. Examples of date-like triples
include `(2013, 2, 1)` and `(0,0,1000)`. A *date* is a date-like
triple whose first part is a positive year (i.e., a year in
the common era), second part is a month between 1 and 12,
and third part is a day between 1 and 31 (or 30, 29, or 28,
depending on the month and year). `(2013, 2, 1)` is a date;
`(0,0,1000)` is not.
The functions you write below need to work correctly only for dates, not for
arbitrary date-like triples. However, you will probably find it easier to
write your solutions if you think about making them work for arbitrary
date-like triples. For example, in your solution to the first problem below,
it's easier to forget about whether the input is truly a date, and simply write
a function that claims (for example) that January 100, 2013 comes before
February 34, 2013—because any date in January comes before any date in
February, but a function that says that January 100, 2013 comes after February
34, 2013 is also valid; behavior on bad dates is unspecified.
You may ignore leap years.
* Write a function `is_before` that takes two dates as input
and evaluates to `true` or `false`. It evaluates to `true`
if the first argument is a date that comes before the second
argument. (If the two dates are the same, the result is `false`.)
* Write a function `string_of_date` that takes a date, and
returns a string representing that date in middle endian
format with the month name spelled out. For example, the
date `(2011,4,22)` would be represented as `"April 22, 2011"`.
* Write a function `earliest : (int*int*int) list ->
(int*int*int) option`. It evaluates to
`None` if the input list is empty, and to `Some d` if date `d`
is the earliest date in the list.
* `earliest` and `max_hp` (above) have a similar specification. Write a
higher-order helper function and use it to reimplement them both.
## Currying
We've already seen that an OCaml function that takes two arguments of types
`t1` and `t2` and returns a value of type `t3` has the type `t1 -> t2 -> t3`.
We use two variables after the function name in the let expression:
```
utop# let add x y = x + y;;
val add : int -> int -> int
```
Another way to define a function that takes two arguments is to write a function
that takes a tuple:
```
utop# let add' t = (fst t) + (snd t)
val add' : int * int -> int
```
or equivalently (and more stylishly):
```
utop# let add'' (x,y) = x + y
val add'' : int * int -> int
```
A third definition uses the curried version of `add`:
```
utop# let add''' (x,y) = add x y
val add''' : int * int -> int
```
Functions written using the first style (i.e. with type `t1 -> t2 -> t3`) are
called "curried" functions, while the second style (with type `t1 * t2 -> t3`)
are called "uncurried". Curried functions are "spicier" because you can
partially apply them (something you can't do with uncurried functions: how do
you pass in half of a pair?). In reality, the term curry does not refer to
spices, but to a man named Haskell Curry (one of a very small set of people
with programming languages named after both their first and last names).
**Exercise**: write uncurried versions of the following library functions,
making use of the curried versions:
- `List.nth`
- `List.append`
- `Char.compare`
- `Pervasives.max`
There should be a pattern to all of your answers to this exercise. When many
functions share a common pattern, you can often write a single higher-order
function to capture the common structure.
**Exercise**: Write a function `uncurry` that takes in a curried
function and returns the uncurried function. Remember that curried functions
have types like `'a -> 'b -> 'c`, and the corresponding uncurried function will
have the type `'a * 'b -> 'c`. Therefore `uncurry` should have the type
```
val uncurry : ('a -> 'b -> 'c) -> ('a * 'b -> 'c)
```
You can use `uncurry` to reimplement the above exercise:
```
let uncurried_nth = uncurry List.nth
let uncurried_append = uncurry List.append
let uncurried_compare = uncurry Char.compare
let uncurried_max = uncurry max
```
**Exercise**: Write the inverse function `curry`. It should have the type
```
val curry : ('a * 'b -> 'c) -> ('a -> 'b -> 'c)
```
## *Roman numerals
*This is a starred problem. We don't expect you to finish the starred problems
from every lab. But they do make excellent study problems for exams.*
We can define a type for [Roman numerals](https://en.wikipedia.org/wiki/Roman_numerals)
in OCaml as follows:
```OCaml
type rnumeral = I | V | X | L | C | D | M
type rnumber = rnumeral list
```
And we can write a function to convert a single Roman numeral to an integer:
```OCaml
let int_of_rnumeral = function
| I -> 1
| V -> 5
| X -> 10
| L -> 50
| C -> 100
| D -> 500
| M -> 1000
```
The letters are usually ordered from greater-valued to smaller-valued.
If that ordering is broken, it means that the immediately preceding
(lower) value is deemed to be negative and should be subtracted
from the higher (out of place) value. For example, IV represents
4, and XC represents 90.
Write a function `int_of_rnumber : rnumber -> int`
that converts a Roman number to an integer.