When to use types or modules in functor signatures?

Learning
5

Thank you for explaining.

I hope I’m not overthinking in the following, but I believe part of my confusion is because I aksed two questions in one. My outer module has three items:

  • a module type Element as an interface description for elements and needed operations on them,
  • a module type S whose role I didn’t think about,
  • a functor Make with an implementation and a specific signature (not necessarily identical to S, but for example S with ….

This is quite similar to Stdlib.Set, which has:

  • a module type regarding elements (OrderedType),
  • some sort of generic “functor output signature” (S),
  • a functor (Make).

The functor Stdlib.Set.Make (Ord) does not strictly have the signature Stdlib.S, but a modified version with an additional type equality constraint. Namely it has the signature S with type elt = Ord.t.

If I understand right, then signature S can help writing modules that require “some sort of set”, idependently of the actual implementation. Exposing the type elt here, allows us to fix it to a specific type, e.g. “I need some set of myelement here.” by writing Stdlib.Set.S with type elt = myelement.

Thus, having elt as part of Set.S seems to be a reasonable choice (not surprisingly).

We also find the type elt in the actual (real) signature of the output of the functor here: Stdlib.Set.Make(..).elt. I guess, it makes sense to include that type here (and not use destructive substitution, for example), because this means the output of the functor will satisfy the signature Stdlib.Set.S (even though it is more specialized through the type equality constraint).

So when I design my outer module (that contains the functor) and I ask myself, “what items do I want to have in my signature”, I need to distinguish between

  • an explicitly exposed module type (S) (if I want one at all),
  • the output signature of my functor (Make) (possibly derived from the aforementioned module type).

These two signatures aren’t necessarily the same. Compare that in Stdlib.Set.S, elt is an abstract type while in Stdlib.Set.Make(M), elt is equal to M.t.

I think to answer my question, I first need to think about: Do I need a module type S that somehow provides an abstraction over functor outputs Make(M)? And which types or modules do I need or want to have exposed there. And then afterwards I can decide which signature a functor Make(M) should have and whether to express it in terms of S.

Let’s assume I don’t need this abstraction. Then I can simply remove S and do something like:

module type Element = sig
  type t

  val compare : t -> t -> int
  val zero : t
end

module Make (Elt : Element) : sig
  (* The following is a local substitution declaration,
     which is not exposed *)
  module Collection := Set.Make(Elt)

  val foo : Collection.t -> Elt.t
end = struct
  module Coll = Set.Make (Elt)

  let foo (c : Coll.t) : Elt.t =
    match Coll.min_elt_opt c with None -> Elt.zero | Some elt -> elt
end

Here, no module and no type is part of the functor’s output signature:

utop # module M = Make (Int);;
module M : sig val foo : Set.Make(Int).t -> int end

A less fancy way to write the example is:

module Make (Elt : Element) : sig
  val foo : Set.Make(Elt).t -> Elt.t
end = struct
  module Coll = Set.Make (Elt)

  let foo (c : Coll.t) : Elt.t =
    match Coll.min_elt_opt c with None -> Elt.zero | Some elt -> elt
end

Resulting in the same signature.

Now say I need or want some possibilities to have an abstraction (module type S) over my implementation, then I believe I might want to include specific types or modules in S, depending on what exactly I want to be abstract about, or what I want to be able to parameterize.