## 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.