Implementation of Functors

Learning
,
1

I’m currently learning about functors in my university course on OCaml.

Right now, I’m having trouble using an instance of a functor, here’s my code ensemble.ml:

(* Signature ELT (element) *)
module type ELT = sig
    type t
    val compare : t -> t -> int
  end

(* Signature S (set) *)
module type S = sig
    type elt
    type t
    val vide : t
    val element_de :  elt -> t -> bool
    val ajout : t -> elt -> t
  end

(* Implementation A of signature ELT *)
module A : ELT = struct
  type t = int
  let compare x y = x - y
end

(* Functor MakeL with signature argument E of type ELT that produces a module S with type elt = E.t (same element type) *)
module MakeL(E : ELT) : S with type elt = E.t
  =
  struct
    type elt = E.t
    type t = elt list
    let vide = []
    let element_de elt t = List.exists (fun e -> (compare e elt) = 0) t
    let ajout t elt = elt :: t
  end

module Test = MakeL(A)
let l1 = [1;4;5]
let l2 = Test.ajout l1 6

When I compile it with ocamlc -c, it outputs

File "ensemble.ml", line 58, characters 20-22:
58 | let l2 = Test.ajout l1 6
                         ^^
Error: This expression has type int list
       but an expression was expected of type Test.t = MakeL(A).t

Am I missing something? I thought l1 is already of type A.t list since A.t = int as implemented.

On a further note, I want to know how to access these fonctors from another file. Let’s say I put the Test module in test.ml. I get the following error:

File "test.ml", line 2, characters 20-21:
2 | module Test = MakeL(A)
                        ^
Error: Unbound module A

How do functors and modules differ from functions when they can’t be accessed from other source files in the same directory when the latter can?

2

I think you want to do one of the following:

module A = struct
  type t = int
  let compare x y = x - y
end

module A : ELT with type t = int = struct
  type t = int
  let compare x y = x - y
end

What you had before was hiding the concrete type of A.t

On a further note, I want to know how to access these fonctors from another file.

The name of a file is implicitly a module name. So if A is in foo.ml, then you would access it with Foo.A

2 Likes
3

One more thing, once you start organizing your code into multiple files, you will save yourself a lot of hassle by using dune to build the project instead of manually typing in ocamlc commands.

4

I apologize, I forgot to mention I already had open Ensemble in the code (the implementations are in ensemble.ml).

5

Never mind, the problem was that l1 wasn’t actually initialised as Test.t. I replaced it with

l1 = Test.vide

and it worked fine.

The issue of accessing the modules from another file is still there. Even with open Ensemble. Can I see a clear example of how it’s done?

6

I’ve copied your code into TryOCaml, see the link here.
If you click on the ‘Eval code’ button, you’ll see what the types are for the various modules.
In particular, you’ll see that module A has type ELT, and if you look at the definition of ELT you’ll see that it never mentions the int type. So the link between A.t and int has been hidden. As @orbitz noted, this is because module A : ELT in the definition explicitly tells the compiler to forget the actual type and use the abstract ELT type instead. If you remove the : ELT annotation you’ll get the link between the types back.

The same happens again for the link between Test.t and int list. If you look at your functor MakeL, here is the type printed in the toplevel:

module MakeL :
  functor (E : ELT) ->
    sig
      type elt = E.t
      type t
      val vide : t
      val element_de : elt -> t -> bool
      val ajout : t -> elt -> t
    end

You can see that it never mentions any lists, so even after fixing the issue with A you’ll get the same error about the type of l1.
Here you have two solutions: either you choose to expose the details of your implementation, to allow the rest of the code to use lists and sets equivalently, or you keep the details hidden and use the functions from your module to create the sets.

Concretely, the first option means adding an extra constraint on the return type of your functor: module MakeL(E : ELT) : S with type elt = E.t and type t = E.t list = ...
The second option means updating the definition of l1: let l1 = Test.ajout (Test.ajout (Test.ajout Test.vide 1) 4) 5

The second option is more idiomatic, but the first option makes it easier to see the values in the toplevel, so it might be interesting for you to experiment with both ideas.

Also, on an unrelated subject, please note that let compare x y = x - y is dangerous, as it will return wrong results in case of overflow (for instance, compare max_int (-1) will return a negative number, implying that max_int is smaller than -1).

2 Likes