Let's bring in our code from last time.
(** An ['a node] is a node of a mutable singly-linked
list. It contains a value of type ['a], and
optionally, a pointer to the next node.*)
type 'a node = {
value: 'a;
mutable next: 'a node option;
}
(** An ['a mlist] is a mutable singly-linked list with
elements of type ['a]. *)
type 'a mlist = {
mutable first: 'a node option;
}
(** [create_node v] is a node containing the value [v]
with no link to another node. *)
let create_node v = {
value = v;
next = None;
}
(** [singleton v] is a singly-linked list containing
exactly one value, [v]. *)
let singleton v = {
first = Some (create_node v)
}
type 'a node = { value : 'a; mutable next : 'a node option; }
type 'a mlist = { mutable first : 'a node option; }
val create_node : 'a -> 'a node = <fun>
val singleton : 'a -> 'a mlist = <fun>
What if we want to add a function that inserts an element at the first value.
(** [insert_first lst n] mutates [lst] by inserting
value [v] as the first value in the list *)
let insert_first lst v =
match lst.first with
| None -> lst.first <- Some (create_node v)
| was_first -> let new_first = create_node v in
new_first.next <- was_first;
lst.first <- Some new_first;;
val insert_first : 'a mlist -> 'a -> unit = <fun>
Let's give it a try!
let l = singleton 3110;;
insert_first l 2110;;
l;;
val l : int mlist = {first = Some {value = 3110; next = None}}
- : unit = ()
- : int mlist =
{first = Some {value = 2110; next = Some {value = 3110; next = None}}}
But we can simplify this! That's the same :)
let insert_first lst v =
lst.first <- Some {value = v; next = lst.first}
val insert_first : 'a mlist -> 'a -> unit = <fun>
let l = singleton 3110;;
insert_first l 2110;;
l;;
val l : int mlist = {first = Some {value = 3110; next = None}}
- : unit = ()
- : int mlist =
{first = Some {value = 2110; next = Some {value = 3110; next = None}}}
What if we wanted to create a function that makes an empty list, instead of a singleton list. Our first instinct might be to do something like this
let empty = {
first = None
}
val empty : '_weak1 mlist = {first = None}
Awesome! Let's test it
let l = empty;;
val l : '_weak1 mlist = {first = None}
insert_first l 3110;;
insert_first l 2110;;
l;;
- : unit = ()
- : unit = ()
- : int mlist =
{first = Some {value = 2110; next = Some {value = 3110; next = None}}}
Awesome, it seems to be working. Now let's make a second list:
let l2 = empty;;
val l2 : int mlist =
{first = Some {value = 2110; next = Some {value = 3110; next = None}}}
Uh oh, since list is mutable, and we're mutating it, we're actually changing the empty list. To fix this, we need to rewrite empty as a function that takes in a unit.
let empty () = {
first = None
}
val empty : unit -> 'a mlist = <fun>
Now, every time empty is called, we get a new empty list:
let l1 = empty ();;
let l2 = empty ();;
insert_first l1 3110;;
insert_first l1 2110;;
l1;;
l2;;
val l1 : '_weak2 mlist = {first = None}
val l2 : '_weak3 mlist = {first = None}
- : unit = ()
- : unit = ()
- : int mlist =
{first = Some {value = 2110; next = Some {value = 3110; next = None}}}
- : '_weak3 mlist = {first = None}