OCaml Modules: bringing (interconnected) types from different modules into a new module

Question

The problem

One problem I'm having is bringing the types and vals of two module into a new combined module. I'll give an example. Currently I have the following two type signatures

module type Ordered =
 sig
  type t (* the type of elements which have an order *)
  val eq : t * t -> bool
  val lt : t * t -> bool
  val leq : t * t -> bool
 end

module type Stack =
 sig
  exception Empty 
  type 'a t (* the type of polymorphic stacks *)

  val empty  : 'a t
  val isEmpty : 'a t -> bool

  val cons  : 'a * 'a t -> 'a t
  val head  : 'a t -> 'a
  val tail  : 'a t -> 'a t
 end

and I'd like to create a module of "stacks for which the basic elements are ordered", i.e.

module type OrderedStack =
 sig 
  exception Empty

  type elem (* the type of the elements in the stack *)
  val eq : elem * elem -> bool
  val lt : elem * elem -> bool
  val leq : elem * elem -> bool

  type t (* the type of monomorphic stacks *)
  val empty  : t
  val isEmpty : t -> bool
  val cons  : elem * t -> t
  val head  : t -> elem
  val tail  : t -> t
 end

Up to here, everything is nice and neat. But now, I'd like to write a functor which takes an Ordered module and a Stack module and produces an OrderedStack module. Something like

module My_functor (Elem : Ordered) (St : Stack): OrderedStack  = 
 struct
  exception Empty

   type elem = Elem.t
  let eq = Elem.eq
  let lt = Elem.lt
  let leq = Elem.leq

  type t = elem St.t
  let empty = St.empty
  let isEmpty = St.isEmpty
  let cons = St.cons
  let head = St.head
  let tail = St.tail
 end

This is exactly what I want and is correct. But it looks like an awful waste of keyboard.

My question

Is there a more compact way to write My_functor above?

What I found out but couldn't put to work

I've seen the include directive in which I could write something like:

module my_functor (Elem : Ordered) (St : Stack): OrderedStack  = 
 struct
  include Elem
  include St
 end

but this has the problem that, for my particular two modules above, both Ordered and Stack have the same type t (although they mean different things in each of them). I'd prefer not to change the original definition of Ordered and Stacks as they are already used in many parts in the code but if you find an alternative formulation for the original two modules that makes it work, that's fine.

I've also seen that the with operator may be relevant here but I couldn't quite work out how it should be used to produce the desired effect. The problem I'm facing is that the types t and 'a t of the two modules Ordered and Stacks and actually connected.

Any ideas?

Answer 1

OrderedStack reuse Ordered definitions, with a slightly different type (elem instead of t). This a cause of redundancy.

You could rather use this OrderedStack signature directly reusing Ordered :

module type OrderedStack = sig
    module Elem : Ordered

    type t
    val empty       : t
    val isEmpty     : t -> bool
    val cons        : Elem.t * t -> t
    val head        : t -> Elem.t
    val tail        : t -> t
end

One other source of redundancy is the fact that you move from a parametric type, 'a Stack.t, to the monomorphic OrderedStack.t. The two types cannot be equated, they are not at all comparable, so there necessarily a translation to make by hand here.

Note that you could decompose the move from (polymorphic) Stack to OrderedStack into one intermediary stack, (monomorphic) MonoStack:

module type MonoStack = sig
  type elem
  type t
  val empty       : t
  val isEmpty     : t -> bool
  val cons        : elem * t -> t
  val head        : t -> elem
  val tail        : t -> t
end

module type OrderedStack = sig
  module Elem : Ordered
  module Stack : MonoStack with type elem = Elem.t
end

Edit

If you don't like the additional indirection of using submodules, which can add some syntactic burden, it is possible of including the modules instead of linking to them. But the problem, as you have noticed, are the name conflict. Starting from OCaml 3.12, we have a new construct in our toolset which allows to rename type components of signatures to avoid conflicts.

module type OrderedStack = sig
  type elem
  include Ordered with type t := elem
  include MonoStack with type elem := elem
end

Second Edit

Okay, I came up with the following solution to bring the Stack/MonoStack bridge. But quite frankly, it's a hack and I don't think it's a good idea.

module type PolyOrderedStack = sig
  module Elem : Ordered
  type t
  type 'a const = t
  module Stack : Stack with type 'a t = 'a const
end

(* 3.12 only *)
module type PolyOrderedStack = sig
  type elem
  include Ordered with type t := elem
  type t
  type 'a const = t
  include Stack with type 'a t := 'a const
end