Stephen taught me a neat trick a while back. Suppose you want to define a some mutually recursive types

type even = Zero | Even_succ of odd and odd = Odd_succ of even

Now suppose you want to do this in such a way that each type belongs to its own module. Since OCaml requires signature annotations in recursive module definitions, I thought this required one to write out the type definitions twice.

module rec Even : sig type t = Zero | Succ of Odd.t end = struct type t = Zero | Succ of Odd.t end and Odd : sig type t = Succ of Even.t end = struct type t = Succ of Even.t end

However, Stephen showed me the following trick

module rec Even : sig type t = Zero | Succ of Odd.t end = Even and Odd : sig type t = Succ of Even.t end = Odd

Whoa! We're seemingly defining some modules out of thin air! This looks very analogous to the ill-founded definitions

let rec even : some_type_for_even = even and odd : some_type_for_odd = odd

But since we're only defining types here, this trick cannot cause undefined values to sneak into our program. We have effectively gotten OCaml to infer the definition of a module from its signature in the special case where the module only contains type definitions (it may also contain module type definitions).

Mutual recursion is not required for this to work. You can also wrap everything up into a single recursively defined parent module if you like.

module rec Layered : sig module Even : sig type t = | Zero | Succ of Layered.Odd.t end module Odd : sig type t = | Succ of Layered.Even.t end end = Layered

Sadly, this trick is somewhat limited in that it doesn't work with our Type_conv pre-processors since there are only type specifications here and not type definitions upon which to hang a "with sexp" (for example).

Is exactly what you are going to do with recursive modules if you are not careful enough:

module rec A : sig val t : unit -> _ end = A

Unless those module are just type definitions I would not implement them that way. I’d go for a more classical implementation:

type even = Zero | Succ of odd

and odd = Succ of even

module Even = struct

type t = even = Zero | Succ of odd

end

module Odd = struct

type t = odd = Succ of even

end

and then you can abstract that with recursive modules if you really want.

module rec Even : sig

type t = Zero | Succ of Odd.t

end

and Odd : sig

type t = Succ of Even.t

end

As an added bonus you can now use type-conv.

I ran into this when trying to define reflective type representations in ocaml (more details in my next post).

Cool! I didn’t know about it. I was using m4 preprocessor to achieve the same effect, e.g. [http://github.com/alavrik/piqi/blob/master/piqicc/boot/piqast.ml.m4]()

BTW, what’s your use case for recursive modules? I use them as a workaround for OCaml’s flat namespace for record labels. With several CamlP4 directives, it is quite handy. For example: [http://github.com/alavrik/piqi/blob/master/piqicc/boot/piqdefs.ml]()