Creating a parametrized module over a parametrized module

Question

I'm trying to write a module that implements algorithms on another module that may be implemented in various ways. So my thinking was to write the first module as

module type Base = sig
  type t
  val f : t -> t
end

Then I write a second module that is parametrised over a module compatible with Base:

module type BasedOnBase = functor (B : Base) -> sig
  type b
  val g : B.t -> b
end

Now I'm trying to write a module that is parametrised over a module that is compatible with BasedOnBase and this is where I'm stuck. My naive approach doesn't work, I've tried

(* won't compile *)

module type Alg = functor (BoB : BasedOnBase) -> sig
  val h : BoB.b -> bool
end

as well as

(* won't compile *)

module type Alg = functor (BoB : functor (B : Base) -> BasedOnBase) -> sig
  val h : BoB.b -> bool
end

but both attempts cause this error:

[...]
Error: Unbound type constructor BoB.b

So I'm obviously missing something here but I can't seem to be able to get my head around the problem. How would I go about achieving what I want, probably in a completely different way?

Answer 1

You can write this:

module type Alg = functor (BoB : BasedOnBase) -> functor (B:Base) -> sig
  type t
  val h : t -> bool
end with type t = BoB(B).b

With this you need to pass a module B:Base when instanciating a module of type Alg, which is not the case in your question.

Edit: or even this:

module type Alg =
  functor (BoB : BasedOnBase) ->
  functor (B : Base) -> sig
    val h : BoB(B).b -> bool
  end