# Data Types and Matching

## Linked lists

OCaml has support for lists built into the language. All elements of a list in OCaml must be the same type. To write a list, use:

``````# [1; 2; 3];;- : int list = [1; 2; 3]
``````

(Note semicolons, NOT commas).

`[]` is the empty list.

A list has a head (the first element) and a tail (the rest of the elements). The head is an element, and the tail is a list, so in the above example, the head is the integer `1` while the tail is the list `[2; 3]`.

An alternative way to write a list is to use the cons operator `head :: tail`. So the following ways to write a list are exactly the same:

``````[1; 2; 3]
1 :: [2; 3]
1 :: 2 :: 
1 :: 2 :: 3 :: []``````

Why do I mention the cons operator? Well, it's useful when we start doing pattern matching on lists, which I'll talk about below.

### The type of a linked list

The type of a linked list of integers is `int list`, and in general the type of a linked list of `foo`s is `foo list`.

This implies that all the elements of a linked list must have the same type. But the type can be polymorphic (ie. `'a list`), which is really useful if you want to write generic functions which operate on "lists of anything". (But note: `'a list` doesn't mean that each individual element has a different type - you still can't use this to construct a list containing, say, a mixture of ints and strings. It means that the type of the elements is anything, but all the same type of anything.)

The `length` function defined as part of the OCaml `List` module is a good example of this. It doesn't matter if the list contains ints or strings or objects or small furry animals, the `List.length` function can still be called on it. The type of `List.length` is therefore:

``List.length : 'a list -> int``

## Structures

C and C++ have the concept of a simple `struct`, short for structure. Java has classes which can be used to similar effect, albeit much more laboriously.

Consider this simple C structure:

``````struct pair_of_ints {
int a, b;
};``````

The simplest equivalent to this in OCaml is a tuple such as `(3, 4)` which has the type `int * int`. Unlike lists, tuples can contain elements of different types, so for example `(3, "hello", 'x')` has type `int * string * char`.

A slightly more complex alternative way of writing a C struct is to use a record. Records, like C structs, allow you to name the elements. Tuples don't let you name the elements, but instead you have to remember the order in which they appear. Here is the equivalent record for our C struct above:

``````# type pair_of_ints = {a : int; b : int};;type pair_of_ints = { a : int; b : int; }
``````

That defines the type, and here is how we actually create objects of this type:

``````# {a = 3; b = 5};;- : pair_of_ints = {a = 3; b = 5}
``````

Note that we use ":" in the type definition and "=" when creating objects of this type.

Here are some examples of this typed into the interactive toplevel:

``````# type pair_of_ints = {a : int; b : int};;type pair_of_ints = { a : int; b : int; }
# {a = 3; b = 5};;- : pair_of_ints = {a = 3; b = 5}
# {a = 3};;Error: Some record fields are undefined: b
``````

So OCaml won't let you leave some fields in your structure undefined.

## Variants (qualified unions and enums)

A "qualified union" doesn't really exist in C, although there is support in the gcc compiler for it. Here is the pattern which one commonly uses for a qualified union in C:

``````struct foo {
int type;
#define TYPE_INT 1
#define TYPE_PAIR_OF_INTS 2
#define TYPE_STRING 3
union {
int i;        // If type == TYPE_INT.
int pair;  // If type == TYPE_PAIR_OF_INTS.
char *str;    // If type == TYPE_STRING.
} u;
};``````

We've all seen this I should think, and it's not a pretty sight. For a start it's not safe: the programmer might make a mistake and accidentally use, say, the `u.i` field when in fact a string was stored in the structure. Also the compiler can't easily check if all possible types have been examined in a switch statement (you can use an `enum` type instead to solve this particular problem). The programmer might forget to set the `type` field, which would result in all sorts of fun and games. Furthermore, it's cumbersome.

Here is the elegant and concise equivalent in OCaml:

``````# type foo =
| Nothing
| Int of int
| Pair of int * int
| String of string;;type foo = Nothing | Int of int | Pair of int * int | String of string
``````

That's the type definition. First part of each `|` separated part is called the constructor. It can be called anything, as long as it starts with a capital letter. If the constructor can be used to define a value, it's followed by the `of type` part, where type always starts with a lowercase letter. In the above example, Nothing is used as a constant and the other constructors are used with values.

To actually create things of this type you would write:

``````Nothing
Int 3
Pair (4, 5)
String "hello"
...``````

Each of these expressions has type `foo`.

Note that you use `of` when writing the type definition, but NOT when writing elements of the type.

By extension, a simple C `enum` defined as:

``enum sign { positive, zero, negative };``

can be written in OCaml as:

``type sign = Positive | Zero | Negative``

### Recursive variants (used for trees)

Variants can be recursive, and one common use for this is to define tree structures. This is where the expressive power of functional languages come into their own:

``````# type binary_tree =
| Leaf of int
| Tree of binary_tree * binary_tree;;type binary_tree = Leaf of int | Tree of binary_tree * binary_tree
``````

Here're some binary trees. For practice, try drawing them on paper.

``````Leaf 3
Tree (Leaf 3, Leaf 4)
Tree (Tree (Leaf 3, Leaf 4), Leaf 5)
Tree (Tree (Leaf 3, Leaf 4), Tree (Tree (Leaf 3, Leaf 4), Leaf 5))``````

### Parameterized variants

The binary tree in the previous section has integers at each leaf, but what if we wanted to describe the shape of a binary tree, but decide exactly what to store at each leaf node later? We can do this by using a parameterized (or polymorphic) variant, like this:

``````# type 'a binary_tree =
| Leaf of 'a
| Tree of 'a binary_tree * 'a binary_tree;;type 'a binary_tree = Leaf of 'a | Tree of 'a binary_tree * 'a binary_tree
``````

This is a general type. The specific type which stores integers at each leaf is called `int binary_tree`. Similarly the specific type which stores strings at each leaf is called `string binary_tree`. In the next example we type some instances into the top-level and allow the type inference system to show the types for us:

``````# Leaf "hello";;- : string binary_tree = Leaf "hello"
# Leaf 3.0;;- : float binary_tree = Leaf 3.
``````

Notice how the type name is backwards. Compare this to the type names for lists, eg. `int list` etc.

In fact it is no coincidence that `'a list` is written "backwards" in the same way. Lists are simply parameterized variant types with the following slightly strange definition:

``type 'a list = [] | :: of 'a * 'a list   (* not real OCaml code *)``

Actually the definition above doesn't quite compile. Here's a pretty-much equivalent definition:

``````# type 'a equiv_list =
| Nil
| Cons of 'a * 'a equiv_list;;type 'a equiv_list = Nil | Cons of 'a * 'a equiv_list
# Nil;;- : 'a equiv_list = Nil
# Cons(1, Nil);;- : int equiv_list = Cons (1, Nil)
# Cons(1, Cons(2, Nil));;- : int equiv_list = Cons (1, Cons (2, Nil))
``````

Recall earlier that we said lists could be written two ways, either with the simple syntactic sugar of `[1; 2; 3]` or more formally as `1 :: 2 :: 3 :: []`. If you look at the definition for `'a list` above, you may be able to see the reason for the formal definition.

## Lists, structures and variants — summary

``````OCaml name      Example type definition        Example usage

list            int list                       [1; 2; 3]
tuple           int * string                   (3, "hello")
record          type pair =                    {a = 3; b = "hello"}
{a: int; b: string}
variant         type foo =
| Int of int                 Int 3
| Pair of int * string       Pair (3, "three")
variant         type sign =
| Positive                   Positive
| Zero                       Zero
| Negative
parameterized   type 'a my_list =
variant           | Empty                      Cons (1, Cons (2, Empty))
| Cons of 'a * 'a my_list``````

## Pattern matching (on datatypes)

So one Really Cool Feature of functional languages is the ability to break apart data structures and do pattern matching on the data. This is again not really a "functional" feature - you could imagine some variation of C appearing which would let you do this, but it's a Cool Feature nonetheless.

Let's start with a real program requirement: I wish to represent simple mathematical expressions like `n * (x + y)` and multiply them out symbolically to get `n * x + n * y`.

Let's define a type for these expressions:

``````# type expr =
| Plus of expr * expr        (* means a + b *)
| Minus of expr * expr       (* means a - b *)
| Times of expr * expr       (* means a * b *)
| Divide of expr * expr      (* means a / b *)
| Value of string            (* "x", "y", "n", etc. *);;type expr =
Plus of expr * expr
| Minus of expr * expr
| Times of expr * expr
| Divide of expr * expr
| Value of string
``````

The expression `n * (x + y)` would be written:

``````# Times (Value "n", Plus (Value "x", Value "y"));;- : expr = Times (Value "n", Plus (Value "x", Value "y"))
``````

Let's write a function which prints out `Times (Value "n", Plus (Value "x", Value "y"))` as something more like `n * (x + y)`. Actually, I'm going to write two functions, one which converts the expression to a pretty string, and one which prints it out (the reason is that I might want to write the same string to a file and I wouldn't want to repeat the whole of the function just for that).

``````# let rec to_string e =
match e with
| Plus (left, right) ->
"(" ^ to_string left ^ " + " ^ to_string right ^ ")"
| Minus (left, right) ->
"(" ^ to_string left ^ " - " ^ to_string right ^ ")"
| Times (left, right) ->
"(" ^ to_string left ^ " * " ^ to_string right ^ ")"
| Divide (left, right) ->
"(" ^ to_string left ^ " / " ^ to_string right ^ ")"
| Value v -> v;;val to_string : expr -> string = <fun>
# let print_expr e =
print_endline (to_string e);;val print_expr : expr -> unit = <fun>
``````

(NB: The `^` operator concatenates strings.)

Here's the print function in action:

``````# print_expr (Times (Value "n", Plus (Value "x", Value "y")));;(n * (x + y))
- : unit = ()
``````

The general form for pattern matching is:

``````match value with
| pattern -> result
| pattern -> result
...``````

The patterns on the left hand side can be simple, as in the `to_string` function above, or complex and nested. The next example is our function to multiply out expressions of the form `n * (x + y)` or `(x + y) * n` and for this we will use a nested pattern:

``````# let rec multiply_out e =
match e with
| Times (e1, Plus (e2, e3)) ->
Plus (Times (multiply_out e1, multiply_out e2),
Times (multiply_out e1, multiply_out e3))
| Times (Plus (e1, e2), e3) ->
Plus (Times (multiply_out e1, multiply_out e3),
Times (multiply_out e2, multiply_out e3))
| Plus (left, right) ->
Plus (multiply_out left, multiply_out right)
| Minus (left, right) ->
Minus (multiply_out left, multiply_out right)
| Times (left, right) ->
Times (multiply_out left, multiply_out right)
| Divide (left, right) ->
Divide (multiply_out left, multiply_out right)
| Value v -> Value v;;val multiply_out : expr -> expr = <fun>
``````

Here it is in action:

``````# print_expr (multiply_out (Times (Value "n", Plus (Value "x", Value "y"))));;((n * x) + (n * y))
- : unit = ()
``````

How does the `multiply_out` function work? The key is in the first two patterns. The first pattern is `Times (e1, Plus (e2, e3))` which matches expressions of the form `e1 * (e2 + e3)`. Now look at the right hand side of this first pattern match, and convince yourself that it is the equivalent of `(e1 * e2) + (e1 * e3)`.

The second pattern does the same thing, except for expressions of the form `(e1 + e2) * e3`.

The remaining patterns don't change the form of the expression, but they crucially do call the `multiply_out` function recursively on their subexpressions. This ensures that all subexpressions within the expression get multiplied out too (if you only wanted to multiply out the very top level of an expression, then you could replace all the remaining patterns with a simple `e -> e` rule).

Can we do the reverse (ie. factorizing out common subexpressions)? We sure can! (But it's a bit more complicated). The following version only works for the top level expression. You could certainly extend it to cope with all levels of an expression and more complex cases:

``````# let factorize e =
match e with
| Plus (Times (e1, e2), Times (e3, e4)) when e1 = e3 ->
Times (e1, Plus (e2, e4))
| Plus (Times (e1, e2), Times (e3, e4)) when e2 = e4 ->
Times (Plus (e1, e3), e4)
| e -> e;;val factorize : expr -> expr = <fun>
# factorize (Plus (Times (Value "n", Value "x"),
Times (Value "n", Value "y")));;- : expr = Times (Value "n", Plus (Value "x", Value "y"))
``````

The factorize function above introduces another couple of features. You can add what are known as guards to each pattern match. A guard is the conditional which follows the `when`, and it means that the pattern match only happens if the pattern matches and the condition in the `when`-clause is satisfied.

``````match value with
| pattern [ when condition ] -> result
| pattern [ when condition ] -> result
...``````

The second feature is the `=` operator which tests for "structural equality" between two expressions. That means it goes recursively into each expression checking they're exactly the same at all levels down.

OCaml is able to check at compile time that you have covered all possibilities in your patterns. I changed the type definition of `type expr` above by adding a `Product` variant:

``````# type expr = Plus of expr * expr      (* means a + b *)
| Minus of expr * expr     (* means a - b *)
| Times of expr * expr     (* means a * b *)
| Divide of expr * expr    (* means a / b *)
| Product of expr list     (* means a * b * c * ... *)
| Value of string          (* "x", "y", "n", etc. *);;type expr =
Plus of expr * expr
| Minus of expr * expr
| Times of expr * expr
| Divide of expr * expr
| Product of expr list
| Value of string
``````

I then recompiled the `to_string` function without changing it. OCaml reported the following warning:

``````# let rec to_string e =
match e with
| Plus (left, right) ->
"(" ^ to_string left ^ " + " ^ to_string right ^ ")"
| Minus (left, right) ->
"(" ^ to_string left ^ " - " ^ to_string right ^ ")"
| Times (left, right) ->
"(" ^ to_string left ^ " * " ^ to_string right ^ ")"
| Divide (left, right) ->
"(" ^ to_string left ^ " / " ^ to_string right ^ ")"
| Value v -> v;;Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Product _
val to_string : expr -> string = <fun>
``````

As you see, the compiler tells you that the new `Product` constructor was not handled.

Exercise: Extend the pattern matching with a `Product` case so `to_string` compiles without warning.