<![CDATA[
# Data types
In this lab we'll practice using records, tuples, and variants. We'll also
introduce another OCaml data type called an *option*, and we'll see a way
to implement dictionaries using lists and pairs that is called an
*association list*.
## Records
##### Exercise: student [✭✭]
Assume the following type definition:
```
type student = { first_name : string ; last_name : string ; gpa : float }
```
Give OCaml expressions that have the following types:
* `student`
* `student -> string * string` (a function that extracts the student's name)
* `string -> string -> float -> student` (a function that creates a student record)
□
Here is a variant that represents a few Pokémon types:
```
type poketype = Normal | Fire | Water
```
##### Exercise: pokerecord [✭✭]
* Define the type `pokemon` to be a record with fields `name` (a string),
`hp` (an integer), and `ptype` (a `poketype`).
* 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.
□
## Options
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 = function
| [] -> ???
| h::t -> max h (list_max t)
```
There are a couple possibilities to consider:
- Return `min_int`. But then `list_max` will only work for integers—
not floats or other types.
- Raise an exception. But then the user of the function has to remember
to catch the exception.
- In Java, you might return `null`. OCaml does not have a `null` value.
Which is actually a good thing: null pointer bugs are not fun to debug.
- In addition to those possibilities, OCaml provides something even better
called an *option.* (Haskellers will recognize options as the Maybe monad.)
You can think of an option as being like a closed box. Either there's something
inside the box, or the box is empty. We don't know which until we open the box.
If there turns out to be something inside the box when we open it, we can take
that thing out and use it.
In `list_max` above, we'd like to metaphorically return a box that's empty
if the list is empty, or a box that contains the maximum element of the list
if the list is non empty.
Here's how we create an option that is like a box with `42` inside it:
```
# Some 42
- : int option = Some 42
```
And here's how we create an option that is like an empty box:
```
# None
- : 'a option
```
The `Some` means there's something inside the box, and it's `42`. The
`None` means there's nothing inside the box.
As for the types we see above, `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. `None`
has type `'a option` because it's unknown what the type is of the thing inside,
as there isn't anything inside.
You can access the contents of an option value `e` using pattern matching.
Here's a function that extracts an `int` from an option, if there is one inside,
and converts it to a string:
```
# let extract o =
match o with
| Some i -> string_of_int i
| None -> "";;
val extract : int option -> string = <fun>
# extract (Some 42);;
- : string = "42"
# extract None;;
- : string = ""
```
Here's how we can write `list_max` with options:
```
let rec list_max = function
| [] -> None
| h::t -> begin
match list_max t with
| None -> Some h
| Some m -> Some (max h m)
end
```
(The `begin`..`end` wrapping the nested pattern match above is not
strictly required here but is not a bad habit, as it will head off
potential syntax errors in more complicated code.)
In Java, every object reference is implicitly an option. Either there
is an object inside the reference, or there is nothing there. That
"nothing" is represented by the value `null`. Java does not force
programmers to explicitly check for the null case, which leads to null
pointer exceptions. OCaml options force the programmer to include a
branch in the pattern match for `None`, thus guaranteeing that the
programmer thinks about the right thing to do when there's nothing
there. So we can think of options as a principled way of eliminating
`null` from the language. Using options is usually considered better
coding practice than raising exceptions, because it forces the caller to
do something sensible in the `None` case.
**Syntax and semantics of options.**
- `t option` is a type for every type `t`.
- `None` is a value of type `'a option`.
- `Some e` is an expression of type `t option` if `e : t`.
If `e ==> v` then `Some e ==> Some v`
##### Exercise: safe hd and tl [✭✭]
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.
Also write a function `safe_tl : 'a list -> 'a list option` that returns
the tail of the list, or `None` if the list is empty.
□
##### Exercise: pokefun [✭✭✭]
Write a function `max_hp : pokemon list -> pokemon option` that, given a list of
`pokemon`, finds the Pokémon with the highest HP.
□
## Tuples
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. You may ignore leap years.
##### Exercise: date before [✭✭]
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`.)
□
##### Exercise: earliest date [✭✭✭]
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. *Hint: use `is_before`.*
□
## Association lists
A *dictionary* is a data structure that maps *keys* to *values*. One
easy implementation of a dictionary is an *association list*, which is a
list of pairs. Here, for example, is an association list that
maps some shape names to the number of sides they have:
```
let d = [ ("rectangle", 4); ("triangle", 3); ("dodecagon", 12) ];;
val d : (string * int) list = (* omitted *)
```
Note that association list isn't so much a built-in data type in OCaml
as a combination of two other types: lists and pairs.
Here are two functions that implement insertion and lookup in
an association list:
```
(* insert a binding from key k to value v in association list d *)
let insert k v d = (k,v)::d
(* find the value v to which key k is bound, if any, in the assocation list *)
let rec lookup k = function
| [] -> None
| (k',v)::t -> if k=k' then Some v else lookup k t
```
The `insert` function simply adds a new map from a key to a value at
the front of the list. It doesn't bother to check whether the key is
already in the list. The `lookup` function looks through the list
from left to right. So if there did happen to be multiple maps
for a given key in the list, only the most recently inserted one
would be returned.
Insertion in an association list is therefore constant time, and lookup
is linear time. Although there are certainly more efficient
implementations of dictionaries—and we'll study some later in this
course—association lists are a very easy and useful implementation for
small dictionaries that aren't performance critical. The OCaml standard
library has functions for association lists in the [`List`
module][list]; look for `List.assoc` and the functions below it in the
documentation.
[list]: http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html
##### Exercise: assoc list [✭]
Use the functions `insert` and `lookup` above to construct an
association list that maps the integer 1 to the string "one",
2 to "two", and 3 to "three". Lookup the key 2. Lookup the key 4.
□
]]>