Having a module and an instance of it as parameters to an OCaml function

user_10664853 0
Viewed 233

I want to write a function that takes modules that implement a certain signature and instances of the same type as those modules, but apparently I can't do that because of an issue related to the scope of the module (the module and it's instance are both parameters, therefore the instance doesn't know the type of the module).

Here is an example:

let f (type a) (module M: Set.S with type elt = a) (pr: a -> unit) (m: M.t) = 
  M.iter pr m;;

Where M is a Set module with elements of type a, and pr can be a printer for elements of type a. And the message of the error caused by it (which I don't find to be super clear):

Line 1, characters 69-78:
Error: This pattern matches values of type M.t
       but a pattern was expected which matches values of type 'a
       The type constructor M.t would escape its scope

I tried to solve this by considering that the problem is caused by the scope of the parameters covering only the body of the function, so I put the last argument inside the body of the function like this:

let f (type a) (module M: Set.S with type elt = a) (pr : a -> unit) =
  fun (m : M.t) ->
    M.iter pr m;;

But the error message is still present:

Line 2, characters 7-16:
Error: This pattern matches values of type M.t
       but a pattern was expected which matches values of type 'a
       The type constructor M.t would escape its scope

So is there a way to do it?

ocaml scope functional-programming
1 Answers

OCaml core language (outside of the module system) is not dependently typed. In fantasy syntax, your function would have type function (module M: Set.S with type elt = 'a) -> ('a -> unit) -> M.t. In this type, M is a value, thus the type is dependently typed, and cannot be implemented in OCaml.

In your case, it is possible to make the type not dependent by restricting the class of modules accepted as arguments with a with constraint

let f (type a t ) (module M: Set.S with type elt = a and type t = t)
  pr m = M.iter pr m
module String_set = Set.Make(String)
let () = f (module String_set) ignore String_set.empty

A possible other solution is to store the value along with the first class module and its existential quantifications:


module type packed = sig
  type a
  module Impl: Set.S with type elt = a
  val value: Impl.t
end

let g (type a) (module P: packed with type a = a)
  pr = P.Impl.iter pr P.value

But for more complex functions, there is no other choices than using functors at the module level.

Aside: if you wonder why the module type Set.S with type elt = a and type t = t in the first variant above is a (necessary) restriction consider this packed module:

let random_int_set: (module Set.S with type elt = int) =
  let compare =
     if Random.int 3 > 1 then Stdlib.compare
     else (fun x y -> Stdlib.compare y x)
  in
  let module S = Set.Make(struct type t = int let compare = compare end) in
  (module S)

Here, the set type is based on a random compare function. Thus the type of set is incompatible with all other Sets. Consequently, it is only possible to use such module with a packed value:

module P = struct
  type a = int
  module Impl = (val random_int_set)
  let value = Impl.empty
end
let () = g (module P) ignore
user_73693660
Related