listocamlcdr

How to get a pointer to the tail of a list in OCaml?

With lisps (e.g. Scheme), one can test whether or not two list tails are identical:

(define ls '(1 2 3))

(define tail1 (cdr ls))  ; Get the tail of the list.
(define tail2 (cdr ls))

(eqv? tail1 tail2)  ; Check if identical. Returns true.

How can an equivalent be implemented in OCaml using references?

Suppose I have this:

let ls = ref [1; 2; 3]
let tail1 : int list ref = get_tail_ref ls
let tail2 : int list ref = get_tail_ref ls
assert (tail1 == tail2)  (* Ensure that they are identical. *)

Is this a correct approach? How can get_tail_ref be defined?

Solution

  • The list type in the OCaml standard library is immutable and you can't do anything with it. Putting a pointer to a list into a mutable cell doesn't make the list itself mutable. Fortunately, you can implement mutable lists, and even follow the lisp data representation, e.g.,

    type ('a,'b) cell = {mutable car : 'a; mutable cdr : 'b}

    The type system will fight with you though :)

    Also, it looks like you're confusing pointers and references. In OCaml, all boxed types (like lists, strings, floats, etc) are represented as pointers. Immediate types, such as int, char, and data constructors, such as None, My_constructor are represented as tagged integers. (It is the same representation all modern lisps are using, btw).

    The reference is just a type defined in the standard library as

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

    So it is a boxed type, that contains a mutable pointer to an arbitrary value. So, for example, you can put a list there, {contents = [1;2]}, and it will contain a pointer to an immutable list. You can change the contents to point to a different list, but you can't change the list itself. Again, there are immutable, and you can't turn something that is immutable to mutable.

    Also, note that OCaml will share data, for example

    let common_tail = [3;4]
let head_one = 1 :: common_tail
let head_two = 0 :: common_tail

    They will both share the same tail, e.g.,

    List.tl head_one == List.tl head_two

    Usually, this is quite innocent, since people don't use mutable data types in OCaml a lot, but you can actually create a list of reference they will be shared too, e.g.,

    let common_tail = [ref 3; ref 4]
let head_one = ref 1 :: common_tail
let head_two = ref 0 :: common_tail

    And if you will now set cadr to 33

    List.hd (List.tl head_two) := 33;;

    It will affect both lists

    # head_one;;
- : int ref list = [{contents = 1}; {contents = 33}; {contents = 4}]

# head_two;;
- : int ref list = [{contents = 0}; {contents = 33}; {contents = 4}]