OCaml: recursion with first-class modules and existential type

Question

I'm trying to make a function that uses two modules (of the same type) alternately while going deeper into recursion. I pass the modules as arguments and everything went wrong when I added an existential type to the module. What surprised me a little is that if I make the function non-recursive (like all remotely similar examples I found), it works.

Here is what I think is the minimal example (just a single module passed around):

module type TEST =
  sig
    type t
    val foo : t -> unit
  end

let rec foo
          (type a)
          (module Test : TEST with type t = a)
          (arg : a) : unit =
   (* Test.foo arg *) (* <- works *)
   (* I tried various type annotations, but none worked: *)
   foo (module Test : TEST with type t = a) (arg : a)

Error message for the example:

Error: This expression has type
         (module TEST with type t = a) -> a -> 'b
       but an expression was expected of type 
         (module TEST with type t = a) -> a -> 'b
       The type constructor a would escape its scope

Why doesn't it work and what can I do to make it work?

Answer 1

Not sure to completely understand your Error, but when doing recursion, it is often better to put the type annotation at the highest level. Here is a version that works:

module type TEST =
sig
  type t
  val foo : t -> unit
end

let rec foo : type a. (module TEST with type t = a) -> a -> unit
  = fun (module Test) arg ->
    if true
      then foo (module Test) arg 
      else Test.foo arg