## 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&eacute;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&eacute;mon with 78 HP and Fire type. * Create a record named metapod of type pokemon that represents a Pok&eacute;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&eacute;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&eacute;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&mdash;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.