Recursive Set in OCaml

Question

how can I manage to define a Set in OCaml that can contains element of its type too?

To explain the problem I have a type declaration for a lot of data types like

type value =
  Nil
| Int of int
| Float of float
| Complex of Complex.t
| String of string
| Regexp of regexp
| Char of char
| Bool of bool
| Range of (int*int) list
| Tuple of value array
| Lambda of code
| Set of ValueSet.t (* this isn't allowed in my case since module is declared later*)

In addition I declare a concrete module for ValueSet later in the same file:

module ValueSet = Set.Make(struct type t = value let compare = Pervasives.compare end)

The problem is that ValueSet has value as it's elt type but value can be a ValueSet so I'm getting troubles while trying to compile it.

All of these declarations are contained in just a file named types.ml (that has it's own interface types.mli but without any ValueSet module decl since I'm not either sure it's possible).

Can this problem be solved in some way?

Answer 1

You can use recursive modules. Language manual uses precisely the same example of recursive set type to illustrate this language feature. Below is a relevant excerpt.

A typical example of a recursive module definition is:

module rec A : sig
                 type t = Leaf of string | Node of ASet.t
                 val compare: t -> t -> int
               end
             = struct
                 type t = Leaf of string | Node of ASet.t
                 let compare t1 t2 =
                   match (t1, t2) with
                     (Leaf s1, Leaf s2) -> Pervasives.compare s1 s2
                   | (Leaf _, Node _) -> 1
                   | (Node _, Leaf _) -> -1
                   | (Node n1, Node n2) -> ASet.compare n1 n2
               end
    and ASet : Set.S with type elt = A.t
             = Set.Make(A)

It can be given the following specification:

module rec A : sig
                 type t = Leaf of string | Node of ASet.t
                 val compare: t -> t -> int
               end
    and ASet : Set.S with type elt = A.t