Ocaml self-reference

Question

I've created type t = Test of int * t ref

How to create any object of type t?

Answer 1

As delnan said, you can use cyclic values :

let rec x = Test (0, ref x)

While recursion is generally used to define functions, it is possible for certain values. This is not possible in general, there are restrictions described in the documentation.

The idea is that this value is heap-allocated, so it is easy to use it recursively : allocate the space for a "Test" constructor first, then you can define its field using for "x" the adress of the allocated constructor, even if it points to a not-yet-fully-defined value. Functions, lazy values, pairs, records, etc., all follow this pattern. Of course, the specification is not so low-level ("heap-allocated" is not defined in the OCaml manual), there is a slightly more restrictive syntaxic specification.

Once you have bootstrapped a value by value recursion, you can build more elaborate values :

let rec x = Test (0, ref x)
let y = Test (1, ref x)
let (Test (_, r)) = x in r := y

You can also do that directly

let rec x = Test (0, ref y)
and y = Test (1, ref x)

It is also possible, though really not recommended, to use a "dummy value" produced by Obj. This is how the Queue module of the standard library is implemented.

An issue with this definition is that the values are cyclic. It can be problematic if you plan to iterate on the "tail" of such values. If you plan to use the int field to keep track of the "tail length" of the structure (0 means the reference is a dummy pointer that shouldn't be followed), this is exactly how the Queue module is implemented.

There are other options possible. You may for example use a model where the nullability of the tail pointer is made explicit by using an option type :

type t' = Test of int * t' option ref

let x = Test (0, ref None)
let y = Test (0, ref (Some x))

let rec length (Test (_, tail)) =
  match !tail with
  | None -> 0
  | Some tl -> 1 + length tl 

In that case, you don't need recursion to bootstrap your type, None is enough. Of course, as option types have an indirection, this comes at a moderate performance cost.

PS : note that for one-constructor types such as this one, you may be better with a record type:

type t = {
  field : int;
  tail : t ref;
 }