Lab: Data types

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:

□

Here is a variant that represents a few Pokémon types:

type poketype = Normal | Fire | Water
Exercise: pokerecord [✭✭]

□

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:

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.

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; look for List.assoc and the functions below it in the documentation.

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.

□