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 refs 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.

7.2.2. Example: Mutable Singly-Linked Lists

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