Arnaud Spiwack wrote:

> Something that naive intuition would allow you to do is something like :
> 
> module GenOrder : OrderedType =
>  struct
>    type t = 'a
>    let compare = compare
>  end

I had a similar problem while developing my OCaml-Reins data structure 
library (first release will be "real-soon-now").  Stephen Weeks offered 
the following solution:  the main idea is that you build a generic core 
module that is parameterized by the maximum number of type variables 
desired.  So for a set, you might define

module BaseSet = struct
   type 'a elt_
   type 'a set_ = Empty | Node of 'a set_ * 'a elt_ * 'a set_
   val empty : 'a set_
   val add : 'a elt_ -> 'a set_ -> 'a set_
   ...
   val compare_ : ('a elt_ -> 'a elt_ -> int) ->
      'a set_ -> 'a set_ -> int
   ...
end

Then, you can create a polymorphic version
module PolySet = struct
   include BaseSet
   type 'a t = 'a set_
   type 'a elt = 'a
   let compare = compare_ Pervasives.compare
   ...
end

or a monomorphic version:
module MonoSet(C : OrderedType) = struct
   type elt = C.t
   type 'a elt_ = elt
   type t = C.t set_
   let compare = compare_ C.compare
end

Thus allowing you to share all of the underlying code with only a little 
boilerplate.

Cheers,
-mike