First class Modules with parametric types (The type constructor F.f would escape its scope)

Question

I am currently playing around with modules, to see in which way they can be used in similar ways to Haskell type classes. Currently I am trying to play around with the functor type class:

module type Functor =
   sig
      type 'a f
      val fmap : ('a -> 'b) -> ('a f -> 'b f)
   end


module IdFunc =
   struct
      type 'a f  = Id of 'a
      let fmap f = fun (Id a) -> Id (f a)
      let runId  (Id a) = a
   end

let outmap (module F : Functor) av = F.fmap f av

However in this case outmap will not be typed correctly, the compiler produces the error The type constructor F.f would escape its scope. I know why this error is caused in this case, but I am not sure how to work around it (because type f is parametrized).

I already tried to use locally abstract types:

let outmap (type s) (module F : Functor with type 'a f = s) f av = F.fmap f av

or

let outmap (type a) (type b) (type fa) (type fb) 
 (module F : Functor with type a f = fa type b f = fb) f av = 
 F.fmap f av

or

let outmap (type s) (module F : Functor with type f = s) f av = F.fmap f av

which all just give me various syntax errors or typing errors.

Is there any way to work around this?

In Haskell this would just be:

outmap : Functor f => (a -> b) -> f a -> f b

what would be the equivalent in ocaml (if any)?

==== EDIT ====

I found one way to get something similar to work:

module type Functor =
   sig
      type a
      type b
      type af
      type bf
      val fmap : (a -> b) -> (af -> bf)
   end

module type FromTo =
   sig
      type a
      type b
   end

module IdFunc =
   functor (FT : FromTo) -> 
   struct
      type a = FT.a
      type b = FT.b
      type 'a f  = Id of 'a
      type af = a f
      type bf = b f
      let fmap f = fun (Id a) -> Id (f a)
      let runId  (Id a) = a
   end

let outmap (type a') (type b') (type af') (type bf') 
   (module F : Functor 
      with type a  = a'  and
           type b  = b'  and
           type af = af' and
           type bf = bf') 
   f av =  F.fmap f av

module M = IdFunc(struct type a = int type b = string end)

let oi = outmap (module M)

let test = oi (fun _ -> "Test") (M.Id 10)

But this looks like a lot of added complexity for something that should probably be much simpler.

Answer 1

I'm afraid you cannot directly express what you are trying to do because it is an example of higher-kinded polymorphism (polymorphism over type constructors) which is not supported in OCaml's core language.

For an explanation of why OCaml's core language cannot support higher-kinded polymorphism see Section 1.1 in Lightweight higher-kinded polymorphism.

Since the module system does support higher-kinded polymophism, the usual solution to this problem is to make outmap a functor rather than a function.

Alternatively, the paper linked above describes a workaround (implemented in the higher library -- available on opam) which essentially uses defunctionalisation at the type-level. Whether this is more convenient than using functors or not depends on your specific use cases.

Answer 2

Using the ideas from the paper mentioned above (assuming you have defined app and Newtype1 as described in the paper or use their higher package from opam), you can define you functor as:

module type Functor = sig
  type t
  val fmap : ('a -> 'b) -> ('a, t) app -> ('b, t) app
end

module Id = Newtype1(struct type 'a t = 'a end)

module IdFunc : Functor with type t = Id.t = struct
  type t = Id.t
  let fmap f x = x |> Id.prj |> f |> Id.inj
end

let runId (x : ('a, Id.t) app) : 'a = Id.prj x

let outmap (type a)
           (module F : Functor with type t = a)
           f av =
  F.fmap f av

For more examples, you can check out https://github.com/hongchangwu/ocaml-type-classes