Is first-class module more powerful than polymorphic record?

A stackoverflow answer says

Speaking of OCaml, underneath the hood, first-class modules are simply a record of functions.

If that’s the case, why not simply use polymorphic records? What’s good about the module abstraction?

Take module type Set.S as an example.

  • First-class module version:
module type S =
    type elt
    type t
    val is_empty: t -> bool
    val add: elt -> t -> t
  • Polymorphic record version:
type ('elt, 't) set_functions_t = {
  is_empty: 't -> bool;
  add: 'elt -> 't -> 't;

Also consider the functor Set.Make.

  • First-class module version:
module Make(Ord: OrderedType) =
    type elt = Ord.t
    type t = Empty | Node of {l:t; v:elt; r:t; h:int}

    let is_empty = function Empty -> true | _ -> false

    let rec add x = function
        Empty -> Node{l=Empty; v=x; r=Empty; h=1}
      | Node{l; v; r} as t ->
          let c = x v in
          if c = 0 then t else
          if c < 0 then
            let ll = add x l in
            if l == ll then t else bal ll v r
            let rr = add x r in
            if r == rr then t else bal l v rr
  • Polymorphic record version. The implementation of make_set_functions is dummy for simplicity:
type 'a ordered_type_functions_t = {
  compare: 'a -> 'a -> int;

type 'a set_t =
| Empty
| Node of {l: 'a set_t; v: 'a; r: 'a set_t; h: int}

let make_set_functions (ord: 'elt ordered_type_functions_t) : ('elt, 'elt set_t) set_functions_t = {
  is_empty = (fun (set: 'elt set_t) -> false);
  add = (fun (new_elem: 'elt) (old_set: 'elt set_t) -> old_set);

It seems that polymorphic records can do what first-class modules do.


For starters, modules can declare fresh types, and polymorphic records cannot.


Good point.

I think this is more about code organization. But modules don’t have to be first-class.

With modules, I can define a functor (let’s say) for the type of hash-consed things of type t, viz.

module Intern(T : sig type it val hash t -> int end) : sig type t ..... end = struct
type t = HC of
.... code to implement a hashtable mapping to t

and then I can apply that functor to two different types to get two different modules, and two different types t. I can apply that functor twice to the same type and get two different types t that are distinct at compile time, even if identical at runtime. An example being (let’s say) strings in a compiler, where I want to have two different namespace for type-names and variable-names. They’re both strings, but I want them distinct as types in my compiler’s code.

I don’t know how I’d do this with records. Also, the values of type t don’t carry any function-pointers – just the data. Whereas with records, the typical way you use 'em is kind fo like O-O: you have to carry along all the function-pointers, and that makes them fatter in memory.

Generativity of types is a feature of modules.


Here’s one example of why generating new types is important, using the set idea from before.

module StringSet = Set.Make (String)

module CaseInsensitiveStringSet = Set.Make (struct
  type t = string
  let compare a b = (String.lowercase_ascii a) (String.lowercase_ascii b)

(There are probably more robust ways to implement a case-insensitive string set, but this is just an example.)

Both of these sets have type elt = string but their t types are not equal. This is good, because we don’t want to create a case-insensitive string set and then try to add an element with the normal string set’s add function. The Set.Make functor takes care of that type inequality for us, since modules are able to declare new types.

But with a record of functions, we lose all guarantees that an arbitrary 'a set record will behave the way we expect. If we try to implement our two string sets that way, then we just end up with two values with equal string set types. We could apply a case-sensitive add to a case-insensitive set, which we don’t want.


@JohnJ @Chet_Murthy
I just realized that I can write the functor Set.Make using polymorphic records. And your examples can be done with polymorphic records.

JohnJ’s example (make_set_functions is the counterpart of the functor Set.Make):

Yes, but a value of type 'a set_t can be treated as either ordered or unordered, right?

Yes. But since here I take the trouble to write make_set_functions etc, I’ll use string_set_functions (or case_insensitive_string_set_functions). I don’t see a problem here.

The point of generative types, is that when you construct a set using case-insensitive-set operations, you cannot hand that set to string-set operations. The type system prevents it. That’s the point of generative types: types that are structurally identical, are still different and values of those types cannot be intermingled.


I think generative types make modules somewhat akin to classes in Java. A module is not just a collection of functions, but data + methods. Is that good?

Great point! I get why FCM is more powerful.

Everything I said above about “modules” was really about modules per se: I rarely if ever use the “first class” nature of modules in OCaml. Sure, it all applies there too, but again, I rarely-if-ever use that.

1 Like

I would not say that, no. A generative type need not have any functions associated with it. (Just making something up) if you declare a type twice – the same identical type – in two different modules, then values of those two types are not interchangeable. And functions that work on the first, will not work on the second. Those functions don’t need to be declarated in the modules where the types were declared.

I hope I’m being clear. It is the types themselves that are distinct. And types can be distinct even if they are identical structurally in every way. This is what I meant by my functor that produces a module of hash-consed strings: if you apply it twice, you want to get two different modules, with two different types, and you want that you cannot intermingle hash-consed values of the first modules, with those of the second module.


Thank you for your patient explanation!

I’m seeing two different questions here, whether or not FCMs are more powerful and whether or not FCMs are more practical. They are certainly more powerful, but I agree that their extra power is often not needed for everyday problems. If you just need to pass some functions around internally without too much fuss, then there’s nothing wrong with creating a record of functions.

But things like FCMs and functors are important when you have a library that other users will access. In that situation, you need to be able to guarantee that your users won’t be able to misuse your library. Creating new types inside modules is an easy way to do that.


Just for the record - other people might not be using FCM in everyday code, but I do it a lot mixed with functional reactive programming. I see the mix of FCM + FRP as a kind of declarative and pure alternative to OO.

In can go more in depth if someone is interested - the overall design is to start programming without FCM and having toplevel reactive values within modules. Then when you need a part of the reactive graph to be instantiated dynamically and potentially run concurrently, then you can make your modules into functors, instantiated as FCMs.

I’m interested in this combination. Do you have any links to code that demonstrate this?

No havn’t got anything opensourced currently, but it’s proven a good design pattern of several of my bigger FRP codebases (a visual synthesizer and a modular synthesizer rhythm-module). If you have any specific questions I’ll be glad to answer them - otherwise I’m thinking of making a blogpost on it at some point.

I don’t have any specific questions. I think I understand the basic idea, so I was mostly just curious to see a concrete example of how you’ve applied/used the pattern you describe. Consider this a +1 vote for a blog post. :smile:

First-class modules appear to be a good deal more powerful than polymorphic records. You might find the talk (and accompanying code) First-class modules: hidden power and tantalizing promises interesting.