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.