I realize this may be a silly question, so please bear with me.
I define a generalized interface for a mutable queue:
module type QUEUE = sig
type item
type t
val make_empty :
unit -> t
val enqueue :
t -> item -> unit
val dequeue :
t -> item option
end
The reason that I do not define type 'a t (that is, use a type variable 'a) is that certain implementations of QUEUE may require a relation or restriction on the element type. For example, for a priority queue I would require that there exists a priority on each element:
module type PRIORITY = sig
type t
val priority :
t -> int
end
module Priority_queue (P : PRIORITY) () = struct
type item = P.t
type t = (* ... *)
end
For a simple first-in-first-out (FIFO) queue, I don’t require any relation: just a type:
module Fifo_queue (K : sig type t end) () = struct
type item = K.t
type t = (* ... *)
end
Now, I would like to define a type with a type variable that contains a FIFO queue:
module My_module = struct
type 'a t = { fifo_queue : (* What do I do? *) };
end
Can I somehow invoke the Fifo_queue functor with the type variable 'a?
That’s not a silly question at all. It’s a bit tricky to achieve though. Something like that might work, but might be really inconvenient to work with:
module type FIFO_QUEUE = sig
type item
type t = …
val enqueue : …
end
module My_module = struct
type 'a t = Foo of {
fifo_mod: (module FIFO_QUEUE with type item = 'a and type t = 'b);
fifo_queue: 'b;
}
Note that as far as I can tell, you need to name the type t with a variable, locally, to speak of it.
Using @c-cube’s idea using first-class modules, here is an example showing how to implement make_empty and enqueue on such a type (which is not trivial because it requires quite a lot of type annotations):
type 'a t =
| Fifo : 'b * (module QUEUE with type item = 'a and type t = 'b) -> 'a t
let make_empty (type a) () =
let module M = Fifo_queue(struct type t = a end) in
Fifo (M.make_empty (), (module M : QUEUE with type item = a and type t = M.t))
let enqueue (type a) ((Fifo (t, (module M))) : a t) (x : a) = M.enqueue t x
You can see the full directly compilable version here
@c-cube, with OCaml 4.06.0, I get the following error when I try to define My_module.t:
Error: Unbound type parameter 'b
@zozozo, this seems to work perfectly. I think it’s possible to remove some type annotations in make_empty though:
let make_empty (type a) () =
let module M = Fifo_queue(struct type t = a end) in
Fifo (M.make_empty (), (module M))
I even generalized the idea to something like:
module Parametric_queue (F : functor (K : sig type t end) () -> QUEUE with type item = K.t) () = struct
type 'a t = Queue : 'b * (module QUEUE with type item = 'a and type t = 'b) -> 'a t
let make_empty (type a) () =
let module M = F (struct type t = a end) () in
Queue (M.make_empty (), (module M))
(* ... More queue definitions. ... *)
end
What hath science wrought?!
It’s exciting that the type system makes this sort of thing possible, but this approach probably can’t scale: I wouldn’t want to define a “conversion module” for every abstract data structure.
Instead, I think the original example should just stick to the module language:
module My_module (K : sig type t end) = struct
module Queue = Fifo_queue (K) ()
type t = { queue : Queue.t; (* ... *) }
end