When to use types or modules in functor signatures?

[jbe]

Say I have a module that works with elements which can be compared and have a default value (zero), according to the following module type:

module type Element = sig
  type t

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

Now I want to create a functor module Make (Elt : Element) : … = struct … end, which can work with diffent elements and different associated functions compare and zero, and which provides its own functionality: a function named foo serving as an example, which maps a Stdlib.Set of those elements to a single element according to some internal rule (here taking the element that is sorted lowest or the default element if the set is empty).

I wonder how I should define the interface of my functor. A simple approach would be this:

module type S1 = sig
  type element
  type collection

  val foo : collection -> element
end

And then provide a functor like this:

module Make1 (Elt : Element) :
  S1 with type element = Elt.t and type collection = Set.Make(Elt).t =
struct
  module Collection = Set.Make (Elt)

  type element = Elt.t
  type collection = Collection.t

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

But there are more options. Consider the following full code example with S1 through S6 and Make1 through Make6:

module type Element = sig
  type t

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

module type S1 = sig
  type element
  type collection

  val foo : collection -> element
end

module type S2 = sig
  module Element : Element

  val foo : Set.Make(Element).t -> Element.t
end

module type S3 = sig
  module Collection : Set.S

  val foo : Collection.t -> Collection.elt
end

module type S4 = sig
  module Element : Element

  type collection = Set.Make(Element).t

  val foo : collection -> Element.t
end

module type S5 = sig
  type element

  module Collection : Set.S with type elt = element

  val foo : Collection.t -> element
end

module type S6 = sig
  module Element : Element
  module Collection : Set.S with type elt = Element.t

  val foo : Collection.t -> Element.t
end

module Make1 (Elt : Element) :
  S1 with type element = Elt.t and type collection = Set.Make(Elt).t =
struct
  module Collection = Set.Make (Elt)

  type element = Elt.t
  type collection = Collection.t

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

module Make2 (Elt : Element) : S2 with module Element = Elt = struct
  module Element = Elt
  module Collection = Set.Make (Element)

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

module Make3 (Elt : Element) :
  S3 with module Collection = Set.Make(Elt) = struct
  module Collection = Set.Make (Elt)

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

module Make4 (Elt : Element) : S4 with module Element = Elt = struct
  module Element = Elt
  module Collection = Set.Make (Element)

  type collection = Collection.t

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

module Make5 (Elt : Element) :
  S5 with type element = Elt.t and module Collection = Set.Make(Elt) =
struct
  type element = Elt.t

  module Collection = Set.Make (Elt)

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

module Make6 (Elt : Element) :
  S6 with module Element = Elt and module Collection = Set.Make(Elt) =
struct
  module Element = Elt
  module Collection = Set.Make (Elt)

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

Is there a “best” way to go? Or does this depend on further questions, and if yes, which ones? What is idiomatic here?

Your advice is appreciated.

[octachron]

Beyond æsthetic criteria, a more important point is that you generally want to avoid carrying copies of functor arguments inside the functor body. Similarly, it is best to avoid instantiating functors over a functor argument inside the functor.

Thus I would propose to define either:

module type S = sig
  type element
  type collection
  val foo : collection -> element
end

module Make(Elt:Element)(C:Collection with elt := Elt.t) : 
  S1 with type element:=Elt.t and type collection := C.t = struct
  ...
end

if you use only a handful of types defined in Elt or C.
Otherwise, using module destructive substitution scales better:

module type S = sig
  module Elt: Element
  module C: Collection
  val foo : C.t -> Elt.t
end

module Make(Elt:Element)(C:Collection with Elt := Elt) : 
  S1 with module Elt:=Elt and module C:=C = struct
  ...
end

Note that both definitions purposefully avoids capturing any of the types of the functor arguments in the signature of the functor body.

[jbe]

Ah, I didn’t know about signature substitution. Thanks!

Since I only want to support different Elements and not different collections, I would guess this is a clean approach then:

module type Element = sig
  type t

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

module type S7 = sig
  module Element : Element
  module Collection : Set.S with type elt = Element.t

  val foo : Collection.t -> Element.t
end

module Make7 (Elt : Element) :
  S7 with module Element := Elt and module Collection := Set.Make(Elt) =
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

That would be okay?

But there are some bits that I don’t understand yet. Why is Stdlib.Set.Make(…).elt exposed in the standard library, but why shouldn’t I expose an element type or Element module? What is the difference here. Maybe I don’t understand it yet.

@octachron

you generally want to avoid carrying copies of functor arguments inside the functor body

I understand what a functor argument is, but what is a copy of the functor argument? You mean if the functor argument is completely included in the functor’s output? In Stdlib.Set.Make, it is include at least partially in the output (as elt), right? That is okay opposed to completely including it? Or is the key point something else here?

@octachron

it is best to avoid instantiating functors over a functor argument inside the functor

What does instantiating a functor “over a functor argument inside the functor” mean? I think I don’t understand the phrase or what the word “over” means here.

[octachron]

@jbe

I understand what a functor argument is, but what is a copy of the functor argument?

I meant this kind of code:

module Make2 (Elt : Element) : S2 with module Element = Elt = struct
  module Element = Elt
  ...
end

where you are copying the Elt module as a submodule in the functor body.

Similarly,

module Make7 (Elt : Element) :
  S7 with module Element := Elt and module Collection := Set.Make(Elt) =
struct
  module Coll = Set.Make (Elt)
  ...
end

is instantiating the Set.Make functor on the Elt argument.

Both practices are losing the module identity of the Elt argument and are likely to generate unintended and hard to debug type conflicts later on.

Thus they are better avoided except if you keep the submodule entirely internal and don’t expose it in the signature of the functor body (or if you are a module system expert).

[jbe]

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.