Recursive functor in OCaml

6
votes

This question is similar to this one, but I want to declare a recursive functor instead of a recursive module. So I have :

An interface A :

module type A = sig
    type t
    val basic_func: ...
    val complex_func: ...
end

A functor ComplexImpl which implements A.complex_func in terms of A.basic_func :

module ComplexImpl (SomeA : A) =
struct
    let complex_impl params =
        SomeA.basic_func ...
        ...
end

Another interface I :

module type I = sig
    type t
    ...
end

And a functor B which takes an argument of type I, implements interface A and uses ComplexImpl to implement complex_func. I would like to write something like this :

(* I can't write 'rec' here *)
module rec B (SomeI : I) :
    A with type t = SomeI.t
= struct
    type t = SomeI.t
    (* this line does not work *)
    module Impl = ComplexImpl(B(I))

    let basic_func (x : t) = ...
    let complex_func (x : t) =
        Impl.complex_impl x
end

But I can't declare a recursive functor...

The only way I found to implement my recursive functor was to parametrize it by itself :

module B (SomeI : I) (CopyOfB : A with type t = SomeI.t) :
    A with type t = SomeI.t
= struct
    type t = SomeI.t
    (* this line works *)
    module Impl = ComplexImpl(CopyOfB)

    let basic_func (x : t) = ...
    let complex_func (x : t) =
        Impl.complex_impl x
end

And use it like this :

module rec RealB = B(SomeI)(RealB)

But the syntax is verbose, not really safe (what if someone puts a parameter different than RealB) and it becomes really tricky if RealB is itself a functor...

2
recursionmoduleocaml

2 Answers

4
votes

There is a syntactic restriction that recursive modules have the form:

module rec Name : module_type = module_expr

which means that recursive functors cannot be declared using:

module rec Name (Arg : module_type) : module_type = module_expr

but must instead be written:

module rec Name : functor (Arg : module_type) -> module_type =
  functor (Arg : module_type) -> module_expr
3
votes

I have found a solution :

module B (SomeI : I) = struct
    (* introduce a recursive module Implementation *)
    module rec Implementation :
        A with type t = SomeI.t
    = struct
        type t = SomeI.t
        (* use Implementation here *)
        module Impl = ComplexImpl(Implementation)

        let basic_func (x : t) = ...
        let complex_func (x : t) =
            Impl.complex_impl x
    end

    (* include the code of Implementation here *)
    include Implementation
end

And I can use it like this :

module RealB = B(SomeI)