Arrays and Mutable Lists

OCaml arrays

OCaml arrays are like references that hold multiple elements instead of one. An n-element array’s elements are designated by indices 0 to n−1.

Core array operations

Operation	Type	Description
Array.make n x	int -> 'a -> 'a array	Create array of size n, all cells = x
Array.init n f	int -> (int -> 'a) -> 'a array	Create array with cell i = f(i)
Array.get a i	'a array -> int -> 'a	Return a[i]
Array.set a i x	'a array -> int -> 'a -> unit	Set a[i] := x

Examples

let aa = Array.init 5 (fun i -> i * 10)
(* [|0; 10; 20; 30; 40|] *)

Array.get aa 3      (* => 30 *)
Array.set aa 3 42   (* aa[3] := 42, returns () *)

Bounds checking

OCaml arrays are bounds-checked. Accessing Array.get ar 20 on a 20-element array raises Invalid_argument "index out of bounds". This is much safer than C, where an array is merely a starting address with no size information, making buffer overrun attacks possible.

Two-dimensional arrays

An n × n identity matrix can be created as an array of arrays:

Higher dimensions are represented similarly by nesting. OCaml arrays cannot grow: if you outgrow an array, you must allocate a new one (typically double the size) and copy the data.

Mutable lists

type 'a mlist =
  | Nil
  | Cons of 'a * 'a mlist ref

A mutable list is like an ordinary list, but the tail pointer is a reference rather than a direct value. This allows in-place modification: you can redirect the tail of a cons cell to point to a different list.

This is analogous to linked data structures taught in algorithms courses, where nodes contain pointers to other nodes. The syntax differs from C/Java, but the principles are the same.

Comparison of list types

Type	Tail	Mutation
'a list (built-in)	Direct 'a list	Immutable
'a seq (lazy)	unit -> 'a seq (thunk)	Not directly; lazily computed
'a mlist (mutable)	'a mlist ref	In-place via :=

A tripos question might ask you to code odds (return alternate elements) for all three list types, or to detect cycles in a mutable list using reference equality (==).