exercises.md

Exercises

{{ solutions }}

{{ ex1 | replace("%%NAME%%", "mutable fields")}}

Define an OCaml record type to represent student names and 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. Then write an expression to mutate Alice's GPA to 4.0.

{{ ex1 | replace("%%NAME%%", "refs")}}

Give OCaml expressions that have the following types. Use utop to check your answers.

• bool ref
• int list ref
• int ref list

{{ ex1 | replace("%%NAME%%", "inc fun")}}

Define a reference to a function as follows:

let inc = ref (fun x -> x + 1)

Write code that uses inc to produce the value 3110.

{{ ex2 | replace("%%NAME%%", "addition assignment")}}

The C language and many languages derived from it, such as Java, has an addition assignment operator written a += b and meaning a = a + b. Implement such an operator in OCaml; its type should be int ref -> int -> unit. Here's some code to get you started:

let ( +:= ) x y = ...

And here's an example usage:

# let x = ref 0;;
# x +:= 3110;;
# !x;;
- : int = 3110

{{ ex2 | replace("%%NAME%%", "physical equality")}}

Define x, y, and z as follows:

let x = ref 0
let y = x
let z = ref 0

Predict the value of the following series of expressions:

# x == y;;
# x == z;;
# x = y;;
# x = z;;
# x := 1;;
# x = y;;
# x = z;;

Check your answers in utop.

{{ ex2 | replace("%%NAME%%", "norm")}}

The Euclidean norm of an $n$-dimensional vector $x = (x_1, \ldots, x_n)$ is written $|x|$ and is defined to be

$$\sqrt{x_1^2 + \cdots + x_n^2}.$$

Write a function norm : vector -> float that computes the Euclidean norm of a vector, where vector is defined as follows:

(* AF: the float array [| x1; ...; xn |] represents the
 *     vector (x1, ..., xn)
 * RI: the array is non-empty *)
type vector = float array

Your function should not mutate the input array. Hint: although your first instinct might be to reach for a loop, instead try to use Array.map and Array.fold_left or Array.fold_right.

{{ ex2 | replace("%%NAME%%", "normalize")}}

Every vector can be normalized by dividing each component by $|x|$; this yields a vector with norm 1:

$$ \left(\frac{x_1}{|x|}, \ldots, \frac{x_n}{|x|}\right) $$

Write a function normalize : vector -> unit that normalizes a vector "in place" by mutating the input array. Here's a sample usage:

# let a = [|1.; 1.|];;
val a : float array = [|1.; 1.|]

# normalize a;;
- : unit = ()

# a;;
- : float array = [|0.7071...; 0.7071...|]

Hint: Array.iteri.

{{ ex2 | replace("%%NAME%%", "norm loop")}}

Modify your implementation of norm to use a loop. Here is pseudocode for what you should do:

initialize norm to 0.0
loop through array
  add to norm the square of the current array component
return sqrt of norm

{{ ex2 | replace("%%NAME%%", "normalize loop")}}

Modify your implementation of normalize to use a loop.

{{ ex3 | replace("%%NAME%%", "init matrix")}}

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 o f creates and returns an n by o matrix m with m.(i).(j) = f i j for all i and j in bounds.

See the documentation for make_matrix for more information on the representation of matrices as arrays.

{{ ex4 | replace("%%NAME%%", "doubly linked list")}}

Implement a data abstraction for a mutable doubly-linked list. Here is a representation type to get you started:

(** 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.
    RI: The list does not contain any cycles. *)
type 'a dlist = {
  mutable first : 'a node option;
  mutable last : 'a node option;
}

Implement at least these operations:

• create an empty list
• insert a new first value
• insert a new last value
• insert a new node after a given node
• insert a new node before a given node
• remove a node
• iterate forward through the list applying a function
• iterate backward through the list applying a function

Hint: draw pictures! Reasoning about mutable data structures is typically easier if you draw a picture.