Implementation of a circular doubly linked list in OCaml

user_14243756 0
Viewed 275

I am attempting to implement a circular doubly linked list using OCaml type declaration. Here is what I have :

type 'a cList = 
{ 
mutable value : 'a; 
mutable left : 'a cList option; 
mutable right : 'a cList option 
}
;;

The problem comes up when I need to declare a first list containing a single element. Because the element cannot be referenced before being assigned, I cannot get the left and right members of the cell to point on itself. The only workaround I have so far is to allow the left and right members to be of type option, set them to None and then modify them so that they point on the cell itself.

let unitClist v = let a = {
                      value = v; 
                      left = None; 
                      right = None
                      }
              in
              a.left <- Some a; 
              a.right <- Some a;
              a
;;

It works, but it is a bit binding to have to work with the option type when you are sure to have a value. Is there a better way to do it ? Thanks in advance.

doubly-linked-list circular-list data-structures ocaml
2 Answers

Apparently you can also define a recursive value directly with a record. By using a rec binding you can refer to the binding recursively in the definition (in certain cases):

type 'a cList = {
  mutable value : 'a; 
  mutable left : 'a cList; 
  mutable right : 'a cList 
}

let unitClist v =
  let rec a = {
    value = v; 
    left = a; 
    right = a
  }
  in a

This is documented in Chapter 8.1 of the OCaml Manual

user_79435640

You could use objects instead, which are late binding and therefore allow self-reference:

object(self)
  method value = v
  method left = self
  method right = self
end

There's a performance cost to this, of course, because all method calls will be dispatched dynamically, but this wouldn't be possible otherwise so that's the essential trade-off. You can't reference something that doesn't yet exist without employing some kind of indirection (edit: which a heap-allocated record already is. See my other answer).

user_79435640
Related