OCaml: circularity between variant type and module definition

Question

I'm switching from Haskell to OCaml but I'm having some problems. For instance, I need a type definition for regular expressions. I do so with:

type re = EmptySet 
    | EmptyWord
    | Symb of char
    | Star of re
    | Conc of re list
    | Or of (RegExpSet.t * bool) ;;

The elements inside the Or are in a set (RegExpSet), so I define it next (and also a map function):

module RegExpOrder : Set.OrderedType = 
    struct
      let compare = Pervasives.compare
      type t = re
    end 
module RegExpSet = Set.Make( RegExpOrder )      
module RegExpMap = Map.Make( RegExpOrder ) 

However, when I do "ocaml [name of file]" I get:

Error: Unbound module RegExpSet

in the line of "Or" in the definition of "re".

If I swap these definitions, that is, if I write the modules definitions before the re type definitions I obviously get:

Error: Unbound type constructor re

in the line of "type t = re".

How can I solve this? Thanks!

Answer 1

You can try to use recursive modules. For instance, the following compiles:

module rec M : 
sig type re = EmptySet
    | EmptyWord
    | Symb of char
    | Star of re
    | Conc of re list
    | Or of (RegExpSet.t * bool) 
end = 
struct
  type re = EmptySet 
    | EmptyWord
    | Symb of char
    | Star of re
    | Conc of re list
    | Or of (RegExpSet.t * bool) ;;
end

and RegExpOrder : Set.OrderedType = 
    struct
      let compare = Pervasives.compare
      type t = M.re
    end 
and RegExpSet : (Set.S with type elt = M.re) = Set.Make( RegExpOrder )