OCaml: is it possible to define mutually recursive data-structures in separate files

Question

I am quite beginner of OCaml. I am wondering how to define mutually recursive data-types in separate files.

I know the following program is legal.

type t1 = A of int | B of t2
and  t2 = C of float | C of t1

Now, I want to define this t1 and t2 in other files for readability (because a lot of util functions are required indivisually).

I also know, I can define t1 and t2 as above by making .mli files and hide the implementation details (just write type t1 and type t2 in .mli files).

But, now I don't want hide them. Does anyone know how to do it?

I hope simple solution (not use complex or magic one...).

Answer 1

In the current implementation of OCaml, the compilation unit dependency graph must be acyclic. Putting it more simply, compilation units (i.e., different files), cannot mutually recursively refer to each other.

This limitation is an over-approximation, as it disallows valid programs, and it kind of contradicts with the intuition, as it is possible to write recursive modules in a single compilation unit. The reason for this limitation comes from the complexity of type checking of a recursive module. A recursive module cannot be type checked as a standalone entity, as it requires the whole set of modules that are involved in the recursion. But OCaml separate compilation system requires each compilation unit to be standalone and typeable. If OCaml weren't using a separate compilation (and link a program as a whole), then it would be possible to implement recursive units.

The partial solution would be to factor parts of the interface that are independent on the mutual recursiveness and implement them in a separate module(s). For example, you can define your types as follows:

type 'b a = A of int | B of 'b
type 'a c = C of float | C of 'a
type t1 = t2 a and t2 = t1 c

Now you can define an acyclic part of the interface for the 'b a. This interface should be general with respect to the 'b type variable (in other words it should not touch it). In our example, it is hard to imagine such interface, but, assuming that the example is synthetic, but for the product types this method will make sense (cf., type 'b a = {a : int; b : 'b} - you can implement all functions that concern the a field).

As a final note, I would like to say that recursive modules are rarely needed in practice, and usually signify a problem in the design. Especially, when it is needed to move definitions in separate modules - that indicates, that abstractions weren't chosen properly. It might be the case of course, that the underlying problem is inherently complex, but this is very rare in real life.