How to mix polymorphic functions with functors in ocaml?

I have a functor to make a Heap module from a Comparable module, and a polymorphic function to apply Prim's algorithm to graphs with arbitrary labels. Ideally I'd like to be able to write something like:

let prim (graph: 'a graph)=
   let module EdgeHeap=Heap.Make(
       struct
           type t='a edge
           ...
       end
   ) in
   ...
   let heap=EdgeHeap.create () in
   ...

but ocamlc says that 'a is unbound. How do I work around this?

Solution

Normally, you'd have prim (along with related functions) in a functor of its own that is parameterized over a graph module signature. I.e. something like:

module type GraphSpec = sig
  type t
  ...
end

module GraphAlgorithms(G: GraphSpec) = struct
  type graph = ...
  module EdgeHeap = Heap.Make(struct
    type t = G.t edge
    ...
  end)
  let prim (g: graph) = ...
  let kruskal (g: graph) = ...
end

This avoids the use of type variables; instead, you pass the type through the GraphSpec functor argument.

But if you just need it for a single function, this may be overkill. You can work around it then by using locally abstract types. A simple example to illustrate how that works:

let min_list (type u) (l: u list) =
  let module S = Set.Make(struct
    type t = u
    let compare = compare
  end) in 
  S.of_list l |> S.min_elt