Types and expressions
---------------------
**Exercise**: Give OCaml expressions that have the following types:
* `bool ref`
* `int list ref`
* `int ref list`
**Exercise**: Define an OCaml record type to represent student
names and grade point averages (GPAs). It should be possible to
mutate the value of a student's GPA.
* Write an expression defining a student with name `"Alice"` and GPA
`3.7`.
* Write an expression to mutate Alice's GPA to `4.0`.
Doubly linked lists
-------------------
**Important note**: mutable data structures are much easier to
get right if you draw a picture.
Consider the following types and functions for mutable *[doubly-linked lists][dll]*:
[dll]: https://en.wikipedia.org/wiki/Doubly_linked_list
```
(* An ['a node] is a node of a mutable doubly-linked list.
* It contains a value of type ['a] and optionally has
* pointers to previous and/or next nodes. *)
type 'a node = {
mutable prev : 'a node option;
mutable next : 'a node option;
value : 'a
}
(* An ['a dlist] is a mutable doubly-linked list with elements
* of type ['a]. It is possible to access the first and
* last elements in constant time. *)
type 'a dlist = {
mutable first : 'a node option;
mutable last : 'a node option;
}
(* [create_node v] is a node containing value [v] with
* no links to other nodes. *)
let create_node v = {prev=None; next=None; value=v}
(* [empty_dlist ()] is an empty doubly-linked list. *)
let empty_dlist () = {first=None; last=None}
(* [create_dlist n] is a doubly-linked list containing
* exactly one node, [n]. *)
let create_dlist n = {first=Some n; last=Some n}
(* [insert_after d n1 n2] mutates dlist [d] by
* inserting node [n2] after node [n1]. *)
let insert_after (d: 'a dlist) (n1: 'a node) (n2: 'a node) : unit =
failwith "unimplemented"
(* [iter_forward d f] on a dlist [d] which has
* elements n1; n2; ... is (f n1); (f n2); ... *)
let iter_forward (d: 'a dlist) (f: 'a -> unit) : unit =
failwith "unimplemented"
(* [iter_backward d f] on a dlist [d] which has
* elements n1; n2; ... is ...; (f n2); (f n1) *)
let iter_backward (d: 'a dlist) (f: 'a -> unit) : unit =
failwith "unimplemented"
```
* Complete the implementations of `insert_after`, `iter_forward`, and
`iter_backward`.
* Write code that constructs a doubly-linked list whose elements are
1, 2, and 3.
* Use `iter_forward` to print the elements of that list in order.
* Use `iter_backward` to print the elements of that list in reverse order.
Equality of refs
----------------
Because refs are mutable, we must make a distinction between "the same
reference" and "different references to equivalent values". You may want to
consider two different references to the same value to be different because
in the future those references may be changed to refer to different values.
On the other hand, you may only care whether the values they refer to are the
same.
OCaml has two different notions of equality.
- **Physical equality** (==) tests
whether two mutable objects (references, records, or arrays) have the same
identity; that is, `r1 == r2` only if modifying `r1` will also cause
modification of `r2`.
- **Structural equality** (=) tests whether the current contents of a reference
are equivalent.
**Exercise**: define `x`, `y`, and `z` as follows:
```
let x = ref 0
let y = x
let z = ref 0
```
Predict the output of the following statements:
```
utop# x == y;;
utop# x == z;;
utop# x = y;;
utop# x = z;;
utop# x := 1;
utop# x = y;;
utop# x = z;;
```
Check your answers.
Arrays
------
OCaml has support for arrays, which generalize a single ref cell to a sequence
of mutable values.
```
utop# let v = [| 0.; 1. |];;
v : float array = [| 0.; 1. |]
utop# v.(0);;
- : float = 0.
utop# v.(0) <- 5.;;
- : unit = ()
utop# v;;
- : float array = [| 5.; 1. |]
```
The [Array module](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html)
contains useful functions for creating and working with arrays.
**Exercise**:
The [Euclidean norm][norm] of an \\(n\\)-dimensional vector
\\(x = (x_1, x_2, \ldots, x_n)\\) is
$$|x| = \sqrt{x_1^2 + \cdots + x_n^2}.$$
[norm]: https://en.wikipedia.org/wiki/Norm_(mathematics)#Euclidean_norm
Every vector can be *normalized* by dividing each component by
\\(|x|\\); this yields a vector with norm 1:
$$normalize(x) = x/|x| = (x_1/|x|, x_2/|x|, \ldots, x_n/|x|)$$
Define the following type:
```
type vector = float array
```
Write a function `normalize : vector -> unit` that normalizes a vector in place.
Loops
-----
When working with arrays, it is often convenient to write
traditional `for` or `while` loops. The "loops" paragraph of
[section 6.7.2 "Control Structures"][manual-control] in the
OCaml manual contains the syntax and semantics of loops. Here
is a brief summary:
[manual-control]: http://caml.inria.fr/pub/docs/manual-ocaml/expr.html#sec124
```
e ::= ...
| while e1 do e done
| for x = e1 to e2 do e done
| for x = e1 downto e2 do e done
```
Each of these three expressions evaluates the expression between `do` and `done`
for each iteration of the loop; `while` loops terminate when `e1` becomes false;
`for` loops execute once for each integer from `e1` to `e2`. All three
expressions evaluate to `()` after the termination of the loop.
**Exercise**: modify your implementation of `normalize` to use
one of these looping expressions.
Because they always evaluate to `()`, they are less general than folds, maps,
or recursive functions. They are typically only used when evaluation produces
side-effects, but can be preferable to folds because they are less cumbersome.
Another class of useful functions for iterating side-effecting computations are
the `iter` functions:
[`List.iter`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html#VALiter),
[`Map.S.iter`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Map.Make.html#VALiter),
[`Array.iter`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html#VALiter),
and so on. These functions are like `map`, but specialized to functions that
return `unit`.
**Exercise**: use `List.iter` and `print_endline` to print a list of strings.
**Exercise (\*)**: The array module contains two functions for creating an array:
`make` and `init`. `make` creates an array and fills it with a default value,
while `init` creates an array and uses a provided function to fill it in. The
library also contains a function `make_matrix` for creating a two-dimensional
array, but it does not contain an analogous `init_matrix` to create a matrix
using a function for initialization.
Write a function `init_matrix : int -> int -> (int -> int -> 'a) -> 'a array
array` such that `init_matrix n m f` creates and returns an `n` by `m` matrix
`m` with `m.(i).(j) = f i j` for all `i` and `j`. See the documentation for
`make_matrix` for more information on the representation of matrices as arrays.