7.2. Mutable Fields#

The fields of a record can be declared as mutable, meaning their contents can be updated without constructing a new record. For example, here is a record type for two-dimensional colored points whose color field c is mutable:

type point = {x : int; y : int; mutable c : string}

type point = { x : int; y : int; mutable c : string; }


Note that mutable is a property of the field, rather than the type of the field. In particular, we write mutable field : type, not field : mutable type.

The operator to update a mutable field is <- which is meant to look like a left arrow.

let p = {x = 0; y = 0; c = "red"}

val p : point = {x = 0; y = 0; c = "red"}

p.c <- "white"

- : unit = ()

p

- : point = {x = 0; y = 0; c = "white"}


Non-mutable fields cannot be updated that way:

p.x <- 3;;

File "[5]", line 1, characters 0-8:
1 | p.x <- 3;;
^^^^^^^^
Error: The record field x is not mutable

• Syntax: e1.f <- e2

• Dynamic semantics: To evaluate e1.f <- e2, evaluate e2 to a value v2, and e1 to a value v1, which must have a field named f. Update v1.f to v2. Return ().

• Static semantics: e1.f <- e2 : unit if e1 : t1 and t1 = {...; mutable f : t2; ...}, and e2 : t2.

7.2.1. Refs Are Mutable Fields#

It turns out that refs are actually implemented as mutable fields. In Stdlib we find the following declaration:

type 'a ref = { mutable contents : 'a }


And that’s why when the toplevel outputs a ref it looks like a record: it is a record with a single mutable field named contents!

let r = ref 42

val r : int ref = {contents = 42}


The other syntax we’ve seen for records is in fact equivalent to simple OCaml functions:

let ref x = {contents = x}

val ref : 'a -> 'a ref = <fun>

let ( ! ) r = r.contents

val ( ! ) : 'a ref -> 'a = <fun>

let ( := ) r x = r.contents <- x

val ( := ) : 'a ref -> 'a -> unit = <fun>


The reason we say “equivalent” is that those functions are actually implemented not in OCaml itself but in the OCaml run-time, which is implemented mostly in C. Nonetheless the functions do behave the same as the OCaml source given above.

Using mutable fields, we can implement singly-linked lists almost the same as we did with references. The types for nodes and lists are simplified:

(** An ['a node] is a node of a mutable singly-linked list. It contains a value
of type ['a] and optionally has a pointer to the next node. *)
type 'a node = {
mutable next : 'a node option;
value : 'a
}

(** An ['a mlist] is a mutable singly-linked list with elements of type ['a].
RI: The list does not contain any cycles. *)
type 'a mlist = {
mutable first : 'a node option;
}

type 'a node = { mutable next : 'a node option; value : 'a; }

type 'a mlist = { mutable first : 'a node option; }


And there is no essential difference in the algorithms for implementing the operations, but the code is slightly simplified because we don’t have to use reference operations:

(** [insert_first lst n] mutates mlist [lst] by inserting value [v] as the
first value in the list. *)
let insert_first (lst : 'a mlist) (v : 'a) =
lst.first <- Some {value = v; next = lst.first}

(** [empty ()] is an empty singly-linked list. *)
let empty () : 'a mlist = {
first = None
}

(** [to_list lst] is an OCaml list containing the same values as [lst]
in the same order. Not tail recursive. *)
let to_list (lst : 'a mlist) : 'a list =
let rec helper = function
| None -> []
| Some {next; value} -> value :: helper next
in
helper lst.first

val insert_first : 'a mlist -> 'a -> unit = <fun>

val empty : unit -> 'a mlist = <fun>

val to_list : 'a mlist -> 'a list = <fun>


7.2.3. Example: Mutable Stacks#

We already know that lists and stacks can be implemented in quite similar ways. Let’s use what we’ve learned from mutable linked lists to implement mutable stacks. Here is an interface:

module type MutableStack = sig
(** ['a t] is the type of mutable stacks whose elements have type ['a].
The stack is mutable not in the sense that its elements can
be changed, but in the sense that it is not persistent:
the operations [push] and [pop] destructively modify the stack. *)
type 'a t

(** Raised if [peek] or [pop] encounter the empty stack. *)
exception Empty

(** [empty ()] is the empty stack *)
val empty : unit -> 'a t

(** [push x s] modifies [s] to make [x] its top element.
The rest of the elements are unchanged. *)
val push : 'a -> 'a t -> unit

(**[peek s] is the top element of [s].
Raises: [Empty] if [s] is empty. *)
val peek : 'a t -> 'a

(** [pop s] removes the top element of [s].
Raises: [Empty] if [s] is empty. *)
val pop : 'a t -> unit
end

module type MutableStack =
sig
type 'a t
exception Empty
val empty : unit -> 'a t
val push : 'a -> 'a t -> unit
val peek : 'a t -> 'a
val pop : 'a t -> unit
end


Now let’s implement the mutable stack with a mutable linked list.

module MutableRecordStack : MutableStack = struct
(** An ['a node] is a node of a mutable linked list.  It has
a field [value] that contains the node's value, and
a mutable field [next] that is [None] if the node has
no successor, or [Some n] if the successor is [n]. *)
type 'a node = {value : 'a; mutable next : 'a node option}

(** AF: An ['a t] is a stack represented by a mutable linked list.
The mutable field [top] is the first node of the list,
which is the top of the stack. The empty stack is represented
by {top = None}.  The node {top = Some n} represents the
stack whose top is [n], and whose remaining elements are
the successors of [n]. *)
type 'a t = {mutable top : 'a node option}

exception Empty

let empty () = {top = None}

let push x s = s.top <- Some {value = x; next = s.top}

let peek s =
match s.top with
| None -> raise Empty
| Some {value} -> value

let pop s =
match s.top with
| None -> raise Empty
| Some {next} -> s.top <- next
end

module MutableRecordStack : MutableStack