Mutable Fields
Contents
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 <- e2Dynamic semantics: To evaluate
e1.f <- e2, evaluatee2to a valuev2, ande1to a valuev1, which must have a field namedf. Updatev1.ftov2. Return().Static semantics:
e1.f <- e2 : unitife1 : t1andt1 = {...; mutable f : t2; ...}, ande2 : 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