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