Ocaml Functors, Modules and Submodules

Apologies for posting such long, non-compilable code. But despite reading several questions and answers on stackoverflow on ocaml's functors, I don't get how to solve this:

Assume I have a very abstract data structure:

ads.mli

module type ENTRY = sig
    type t
    val get_index : t -> int
    val compare : t -> t -> int
end

module type T = sig
    type entry
    type t
    val cr开发者_如何学Pythoneate : unit -> t
    val insert : entry -> t -> t
    val delete : entry -> t -> t
end

Based on this, I can make concrete data structures on these abstract implementation by passing a functor. For example I made:

concrete_ads.mli

module Make (Entry: Ads.ENTRY) : (ads.T with type entry = Entry.t)

This work, I can now use my implementation in other source-files, for example like this:

module AT = Concrete_ads.Make( 
    type t = int * int;; 
    let get_index = fst;; 
    let to_string = (fun (x,y) -> Printf "%i, %i" x y);; 
end);;

And, then, use the implemenation like:

let at = AT.create () in
let ati = AT.insert (1,2) at in
let atd = AT.delete (1,2) ati in

... etc.

Now, I want write several functions that operate on these data structures in a seperate sourcefile, and they should be accesible from outside. But, I do not know how to declare the type of these functions. Something like this:

search.mli

val search : Int -> Ads.T -> int list

But, when compiling I get:

 Failure: "invalid long identifier type"

I, then, thought I need to specifically declare the module of adt as a submodule in search.mli, something like:

search.mli

module AD = Ads;;
 ...
val search : Int -> AD.T -> int list

But, I get:

Parse error: [module_declaration] expected after [a_UIDENT] (in [sig_item])

What am I missing here ? I feel I either fail with the syntax, or did not fully grasp the concept of Functors, Modules and Submodules ...

Edit Thank you so much for your explanation, gasche! With your example I was able to write what I inteded. I'll post it here for clarification, since there seems to be alot of confusion about functors in ocaml.

In fact I wanted to make the function abstract with respect to Ads.T, but require a specific type for Ads.T.t.

I now have search.mli:

module Make (T : Ads.T with type entry = int * int) : sig
    val search : T.t -> int -> int
end;;

And, in search.ml:

module Make (T : Ads.T with type entry = int * int) : sig
    val search : T.t -> int -> int 
end = struct
    (* actual implementation of search *)
end;;

And it worked exactly as I intended.

What are you trying to do exactly? Do you want your function to be parametrized over an ad type (eg. Ads.T.t), or over an ad module (eg. Ads.T) ?

In both cases, you should wrap those generic functions in modules:

module Generic (Ad : Ads.T) : sig
  val search : int -> Ad.t -> int list
end = struct
  let search _ _ = assert false
end

You can then instantiate them easily, eg. to work with your Conrete_ads modules:

module AT = Concrete_ads.make(struct ... end)
module Lib = Generic(AT)
let foo = Lib.search 2 (AT.create ())

Of course, if you would just like your functions to be parametrized over a specific, concrete type:

val search : int -> AT.t -> int list

PS: in your definition of AT, you forgot the struct in the struct .. end module argument of the functor.

PPS: with OCaml 3.12 there is a new shiny thing called first-class modules that allows to pass a module as a value argument to a function

val search : int -> (module Ad.T) -> int list

let search n ad_module =
  let module Ad = (val ad_module : Ad.T) in
  ... Ad.foo ..

... search 2 (module AT : Ad.T) ...

(Explanation : module S, as a type expression, is the type of values that are "reified modules" of signature S; (val t : S), as a module expression, is the module that was packed into the value t, with signature S. Here I take ad_module as a value and unpack it into the Ad module locally, which can then be used as any other module inside the function. Finally, (module M : S) is a term expression that packs the module M with signature S into a value.)

It can supplement using a functor in some cases, but as it is new, a bit more complex (there are non-trivial limitations on the use of first-class modules) and possibly going to change a bit in the next language versions, I would advise keeping the tried-and-true functor construction.