On this page

OCaml Recursive Modules: A Complete Guide

Published on September 15, 2026

Enrico Hochkoeppler Profile

By Enrico Hochkoeppler

Web Developer & TutoriaLibre Founder

Recursive modules allow two or more modules to refer to each other, solving circular dependencies that ordinary module definitions cannot express. The module rec ... and ... syntax enables this, but the OCaml compiler imposes a strict "safe module" restriction to guarantee that evaluation terminates. This article explains the syntax, the evaluation model, the compile-time and runtime errors that arise from ill-founded definitions, and the practical alternatives that often eliminate the need for recursion altogether.

The Problem of Circular Module Dependencies​

Ordinary OCaml modules are defined sequentially. Each module can refer to previously defined modules, but it cannot refer to a module that is defined later. This sequential discipline is simple and predictable, but it breaks down when two data structures genuinely need to mention each other.

Consider a tree whose nodes contain a set of subtrees. The type of the tree refers to the type of the set, and the type of the set refers back to the type of the tree. Without a mechanism for mutual recursion, this circularity cannot be expressed directly.

A similar situation arises with mutually recursive types across module boundaries. A module defining even numbers might need the type of odd numbers, while the module defining odd numbers needs the type of even numbers. Splitting these definitions into separate modules creates a dependency cycle that ordinary module syntax rejects.

Recursive modules were introduced in Objective Caml 3.07 to address precisely these cases. They remain an experimental extension of the language: the class of recursive definitions accepted, as well as the dynamic semantics, are not final and may change in future releases.

The module rec Syntax​

Recursive module definitions are introduced by the module rec ... and ... construction. This construction generalizes regular module definitions by allowing the defining module expressions and module types to refer recursively to the module identifiers being defined.

The basic form is:


module rec ModuleName1 : ModuleType1 = ModuleExpr1

and ModuleName2 : ModuleType2 = ModuleExpr2

The rec keyword after module signals that the definitions that follow may refer to each other. Each module definition is separated by and. A signature may also be given, as shown above, and the signature itself may refer to the other modules in the recursive group.

The same construction applies to module types:


module type rec ModuleTypeName1 = ModuleTypeExpr1

and ModuleTypeName2 = ModuleTypeExpr2

In the specification case, module types must be parenthesized if they use the with mod-constraint construct. This syntactic requirement prevents ambiguity in the grammar.

The Canonical Example: Trees and Sets​

The OCaml manual uses a tree-and-set example to illustrate recursive modules. The tree type has leaves containing strings and nodes containing sets of trees. The set is produced by applying the Set.Make functor to the tree module itself.


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) -> Stdlib.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)

The module A defines the tree type. Its Node constructor carries a value of type ASet.t. The module ASet is defined by applying Set.Make to A. The Set.Make functor produces a module that satisfies Set.S with element type A.t.

This definition is accepted because the dependency cycle between A and ASet passes through a safe module. The concept of a safe module is central to how recursive modules work, and it is explained in the next section.

The same recursive definition can be written as a 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

Specifications are useful when the implementation is provided elsewhere, such as in a separate compilation unit or through a functor.

The Safe Module Requirement​

The OCaml compiler requires that every dependency cycle between recursively defined modules passes through at least one "safe" module. A module is safe if all value definitions it contains have function types of the form typexpr1 -> typexpr2.

In other words, a safe module contains only functions as values. It may contain types, exceptions, and other non-value components, but every value binding must be a function. A module with no value definitions is vacuously safe.

The safety requirement exists to guarantee that the recursive definition can be evaluated without accessing uninitialized data. When a module is safe, the compiler can create a dummy value for each function before the module is fully evaluated. These dummy functions raise the Undefined_recursive_module exception if they are called prematurely. Once the module's real values are computed, the dummy values are replaced.

If a dependency cycle contains no safe module, the compiler rejects the definition with an error. For example:


module rec M : sig val x : int end = struct

  let x = N.y

end

and N : sig val x : int val y : int end = struct

  let x = M.x

  let y = 0

end

Both M and N contain non-function values. Neither is safe, so the cycle M -> N -> M has no safe module. The compiler reports:


Error: Cannot safely evaluate the definition of the following cycle

of recursively-defined modules: M -> N -> M.

There are no safe modules in this cycle (see manual section 8.2).

Module M defines an unsafe value, x.

Module N defines an unsafe value, x.

The error message identifies the unsafe values that cause the rejection. In this case, x is a non-function value in both modules.

Evaluation Semantics and the Undefined_recursive_module Exception​

When a recursive module definition is accepted, evaluation proceeds in three phases. First, the compiler builds initial values for the safe modules involved. Every functional value in a safe module is bound to a dummy function fun _ -> raise Undefined_recursive_module. Second, the defining module expressions are evaluated. Third, the initial dummy values for the safe modules are replaced by the values computed in the second phase.

If a function component of a safe module is applied during the second phase, the Undefined_recursive_module exception is raised at runtime. This situation corresponds to an ill-founded recursive definition: the function is being called before the data it depends on has been initialized.

The manual provides the following example:


module rec M : sig

  val f : unit -> int

end = struct

  let f () = N.x

end

and N : sig

  val x : int

end = struct

  let x = M.f ()

end

Here, M is safe because its only value f is a function. N is unsafe because x is an integer value. The cycle passes through the safe module M, so the definition is accepted by the compiler. However, during the evaluation of N, the expression M.f () is evaluated. At that moment, f is still the dummy function that raises Undefined_recursive_module. The result is a runtime exception:


Exception: Undefined_recursive_module ("exten.etex", 1, 43).

This example illustrates a critical point: the compiler's safety check is a static approximation. It guarantees that the definition can be evaluated, but it cannot guarantee that the functions will not be called too early. Avoiding such calls is the programmer's responsibility.

In the tree-and-set example, the definition is well-founded because Set.Make(A) does not call A.compare during its own initialization. It stores the comparison function for later use. The function is only called when elements are actually inserted into or looked up in the set, which happens after the recursive module definition has been fully evaluated.

Common Pitfalls and Limitations​

Recursive modules are a powerful feature, but they come with several restrictions that developers frequently encounter.

The first restriction is that signatures must be written explicitly. OCaml cannot infer the signature of a recursive module, so every module in the recursive group must be annotated with a signature. This is a common source of frustration, because it means duplicating type information between the signature and the implementation.

The second restriction is that recursive modules cannot span multiple files. A recursive module definition must appear within a single compilation unit. Mutually recursive modules defined in separate .ml files are not supported by the standard compiler. The experimental recursive packs feature, described in an OCamlPro blog post, aims to remove this limitation by allowing recursive compilation units through packs, but it is not part of the stable language.

The third restriction concerns nested modules. Mixing nested modules with recursive modules can lead to unexpected behavior. A discussion on the OCaml forums describes a case where a recursive module contains pointers to other recursive modules as subfields. The initialization process creates distinct dummy modules for each recursive module, and patching the functions one by one does not correctly wire the nested module references. The result is an Undefined_recursive_module exception at runtime, even though the definition appeared to be well-formed.

The fourth restriction concerns functor application. The approximation phase of recursive module typechecking skips parts of signatures such as value declarations and the right-hand side of type declarations. This can cause functor applications inside recursive modules to be mis-approximated, leading to type errors in situations that appear correct.

These limitations mean that recursive modules should be used with care and only when simpler alternatives are not sufficient.

Alternatives to Recursive Modules​

In many cases, the circular dependency that seems to require recursive modules can be eliminated by restructuring the code.

Separating Types from Functions​

The most common alternative is to separate type definitions from the functions that operate on them. If the circularity only involves types, the types can be defined together in a single module or in a mutually recursive type definition. The functions can then be defined in separate modules that take the type-defining module as a parameter.

For example, instead of defining a tree module and a set module recursively, one can define the tree type in a module TreeTypes, then define a comparison function, then apply Set.Make to a module that combines TreeTypes with the comparison function. This approach avoids recursive modules entirely.

The Recursive Signatures Trick​

A technique described on the Jane Street blog uses recursive signatures to achieve a similar effect without recursive module definitions. The idea is to define a module signature that recursively refers to itself, then use that signature to constrain a module that contains the implementation. This trick works when the recursive dependency is primarily at the type level and does not require the full generality of recursive module evaluation.

First-Class Modules​

First-class modules allow modules to be passed as values at runtime. This provides another way to break dependency cycles: a function can receive a module as an argument, and that module can in turn refer to the function's context. First-class modules are more flexible than recursive modules in some respects, but they introduce runtime overhead and are not always appropriate.

Recursive Packs​

For projects that genuinely need mutually recursive compilation units across multiple files, the recursive packs feature being developed by OCamlPro and Jane Street may eventually provide a solution. This feature allows packs to be compiled as recursive modules, using new compiler options such as -recursive and -recursive-pack. As of this writing, it remains experimental.

When to Use Recursive Modules​

Recursive modules are the right tool when a data type's definition genuinely requires a module that is parameterized by that type. The tree-and-set example is the canonical case: the set module needs the tree type as its element type, and the tree type needs the set module for its node constructor. No amount of restructuring can eliminate this circularity without changing the data structure itself.

Recursive modules are also useful when building interpreters or compilers where the abstract syntax tree and the environment are mutually recursive. The environment maps identifiers to values, and values may contain syntax trees, creating a cycle that recursive modules can express.

In all other cases, simpler alternatives should be preferred. The explicit signatures, single-file restriction, and tricky evaluation semantics make recursive modules a sharp tool that is best reserved for problems that cannot be solved otherwise.

Key Takeaways​

Recursive modules solve a genuine problem: circular dependencies between modules that cannot be restructured away. The module rec ... and ... syntax enables these definitions, but the compiler enforces a safety condition that requires at least one module in every cycle to contain only function values. Evaluation of recursive modules uses dummy functions that raise Undefined_recursive_module if called prematurely, and the programmer must ensure that no such calls occur during initialization. The feature is experimental, has significant limitations, and should be used only when simpler alternatives such as separating types from functions, recursive signatures, or first-class modules are insufficient.

Frequently Asked Questions​

What is a recursive module in OCaml?

A recursive module is a module definition that can refer to other modules in the same recursive group. It is introduced by the `module rec ... and ...` syntax and allows mutual dependencies between modules that ordinary sequential definitions cannot express.

What is a safe module?

A safe module is a module in a recursive definition where all value definitions have function types. The compiler requires that every dependency cycle passes through at least one safe module to guarantee that the definition can be evaluated.

What does Undefined_recursive_module mean?

It is an exception raised at runtime when a function from a safe module is called during the initialization of a recursive module definition, before the function has been replaced with its real implementation. It indicates an ill-founded recursive definition.

Can recursive modules span multiple files?

No. Standard OCaml requires recursive modules to be defined within a single compilation unit. The experimental recursive packs feature aims to remove this restriction but is not part of the stable language.

When should recursive modules be used instead of functors?

Recursive modules should be used when a module depends on a type defined in another module, and that other module in turn depends on the first module. Functors are preferable when the dependency can be expressed as a parameter rather than a cycle.

Found this helpful? Share the knowledge...

... or support this project to keep it alive!

Buy Me a Coffee

Previous

Functors

Next

Extensible Variants and Exn Patterns