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.