# Going from a type variable to the argument of a functor

**URL:** <https://discuss.ocaml.org/t/going-from-a-type-variable-to-the-argument-of-a-functor/1490>\
**Category:** Learning\
**Created:** [January 26, 2018, 4:14pm UTC](https://discuss.ocaml.org/t/going-from-a-type-variable-to-the-argument-of-a-functor/1490 "2018-01-26T16:14:12Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![jhaberku](https://avatars.discourse-cdn.com/v4/letter/j/5f8ce5/32.png) [@jhaberku](https://discuss.ocaml.org/u/jhaberku)\
**Post date:** [January 26, 2018, 4:14pm UTC](https://discuss.ocaml.org/t/going-from-a-type-variable-to-the-argument-of-a-functor/1490/1 "2018-01-26T16:14:12Z")

</div>

I realize this may be a silly question, so please bear with me.

I define a generalized interface for a mutable queue:

```auto
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:

```auto
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:

```auto
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:

```auto
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`?

---

<div class="post-metadata">

**Author:** ![c-cube](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/c-cube/32/1727_2.png) [@c-cube](https://discuss.ocaml.org/u/c-cube)\
**Post date:** [January 26, 2018, 5:22pm UTC](https://discuss.ocaml.org/t/going-from-a-type-variable-to-the-argument-of-a-functor/1490/2 "2018-01-26T17:22:19Z")

</div>

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:

```ocaml

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.

---

<div class="post-metadata">

**Author:** ![zozozo](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/zozozo/32/59_2.png) [@zozozo](https://discuss.ocaml.org/u/zozozo)\
**Post date:** [January 26, 2018, 5:40pm UTC](https://discuss.ocaml.org/t/going-from-a-type-variable-to-the-argument-of-a-functor/1490/3 "2018-01-26T17:40:09Z")

</div>

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):

```ocaml
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](https://gist.github.com/Gbury/46f5dfbd7f336a53dc56008b9d83f139)

---

<div class="post-metadata">

**Author:** ![jhaberku](https://avatars.discourse-cdn.com/v4/letter/j/5f8ce5/32.png) [@jhaberku](https://discuss.ocaml.org/u/jhaberku)\
**Post date:** [January 27, 2018, 3:18pm UTC](https://discuss.ocaml.org/t/going-from-a-type-variable-to-the-argument-of-a-functor/1490/4 "2018-01-27T15:18:47Z")

</div>

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:

```auto
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:

```auto
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:

```auto
module My_module (K : sig type t end) = struct
  module Queue = Fifo_queue (K) ()

  type t = { queue : Queue.t; (* ... *) }
end

```