Going from a type variable to the argument of a functor

Learning
#1

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?

#2

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.

3 Likes
#3

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

3 Likes
#4

Thanks to both of you!

@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
1 Like