let square (x:int) : int = x * x let l : int list = [1;4;9]
let k : int list = [0;1;4;9]
List types
The example just above uses the type annotation l : int list to indicate that
l is a list of int values. Similarly, we can have a list of strings whose type is
string listor a list ofbool lists, whose type is(bool list) list.
All of the elements of a list must be of the same type: OCaml supports only
“homogeneous” lists. If you try to create a list of mixed element types, such as
3::"hello"::[], you will get a type error. While this may seem limiting, it is ac-tually quite useful; knowing that you have a list ofints, for example, means that you can perform arithmetic operations on all of those elements without worrying about what might happen if some non-integer element is encountered.
Simple pattern matching on lists
We have seen how to construct lists by using ::. How do we take a list value apart? Well, there are only two cases to consider: either a list is empty, or it has some head element followed by some tail list. In OCaml we can express this kind of case analysis using pattern matching. Here is a simple example that uses case analysis to determine whether the listlis empty:
let l : int list = [1;2;3]
let is_l_empty : bool = begin match l with
| [] -> true
| x::tl -> false end
The begin match hexpi with ... end expression compares the shape of the value computed by hexpi against a series of pattern cases. In this example, the first case is| [] -> true, which says that, if the list being analyzed is empty, then the result of thematchshould betrue.
The second case is| x::tl -> false, which specifies what happens if the the list being analyzed matches the patternx::tl. If that happens, then the expression to the right of the->in this branch will be the result of the wholematch.
Note that the patterns [] andx::tl look exactly like the two possible ways of constructing a list! This is no accident: since all lists are built from these construc-tors, these are exactly the cases that we have to handle—no more, and no less. The difference between the pattern x::tland a list value is that in the pattern, x and
tlare identifiers (i.e. place holders), similar to the identifiers bound bylet. When thematchis evaluated, they are bound to the corresponding components of the list, so that they are available for use in the expression following the pattern’s->.
To see how this works, let’s look at some examples. First, let’s see how to eval-uate the example above, which doesn’t actually use the identifiers bound by the pattern:
let l : int list = [1;2;3]
let is_l_empty : bool = begin match l with
| [] -> true
| x::tl -> false end
7−→ (by substituting[1;2;3]forl)
let l : int list = [1;2;3]
let is_l_empty : bool = begin match [1;2;3] with
| [] -> true
| x::tl -> false end
At this point, we match the list [1;2;3] against the first pattern, which is []. Since they don’t agree—[]doesn’t have the same shape as[1;2;3]—we continue to the next case of the pattern. Now we try to match the pattern x::tl against
[1;2;3]. Remember that [1;2;3] is just syntactic sugar for 1::2::3::[], which, if we parenthesize explicitly, is just 1::(2::(3::[])). This value does match the patternx::tl, lettingxbe1andtlbe2::3::[]. Therefore, the result of this pattern match is the right-hand side of the ->, which in this example is just false. The entire program thus steps to:
let l : int list = [1;2;3]
let is_l_empty : bool = false
In more interesting examples, the identifiers like x and tl that are used in a cons-pattern will also appear in the right-hand side of the match case. For example,
here is a function that returns the square of the first element of anint list, or-1 if the list is empty:
let square_head (l:int list) : int = begin match l with
| [] -> -1
| x::tl -> x * x end
Let’s see how a call to this function evaluates:
square_head [3;2;1]
7−→ (by substituting[3;2;1]forlin the body ofsquare_head)
begin match [3;2;1] with
| [] -> -1
| x::tl -> x * x end
Now we test the branches in order. The first branch’s pattern ([]) doesn’t match, but the second branch’s pattern does, with x bound to 3 and tl bound to [2;1], so we substitute 3 for x and [2;1] for tl in the right-hand side of that branch, i.e.:
begin match [3;2;1] with
| [] -> -1
| x::tl -> x * x end
7−→ (substitute3forxand[2;1]fortl) in the second branch
3 * 3
7−→
9
3.2 Recursion
The definition of lists that we gave at the start of this chapter said that a list is either
[] the empty list, sometimes called nil, or
v::tail a valuevfollowed bytail, a list of the remaining elements.
Note that this description of lists is self referential: we’re defining what lists are, but the second clause uses the word “list”! How can such a “definition” make sense?
The trick is that the above definition tells us how to build a list of length 0 (i.e. the empty list[]), or, given a list of length n, how to construct a list of length n + 1. The phrase “list of the remaining elements” is really only talking about strictly shorter lists.
This is the hallmark of an inductive data type: such data types tell you how to build “atomic” instances (here, []) and, given some smaller values, how to con-struct a bigger value out of them. Here, :: tells us how to construct a bigger list out of a new head element and a shorter tail.
This pattern in the structure of the data also suggests how we should compute over it: using structural recursion. Structural recursion is a fundamental concept in computer science, and we will see many instances of it throughout the rest of the course.
The basic idea is simple: to create a function that works for all lists, it is suffi-cient to say what that function should compute for the empty list, and, assuming that you already have the value of the function for the tail of the list, how to compute the function given the value at the head. Like the definition of the list data type, functions that compute via structural recursion are themselves self referential—the function is defined in terms of itself, but only on smaller inputs!