Where can I find resources to learn more about functors in ReScript (or OCaml)?

1

Also, I’d like to better understand why we need functors for things like Maps in the example code below.

module IntCmp = Belt.Id.MakeComparable({
  type t = int
  let cmp = (a, b) => Pervasives.compare(a, b)
})

let m = Belt.Map.make(~id=module(IntCmp))

Belt.Map.set(m, 0, "a")

Are there any books, courses, etc. that are recommended?

2

There is a chapter about functors in the online version of the book “Real World OCaml” that may help: Functors - Real World OCaml

However, I have not found any resources about functors for ReScript yet, besides the official documentation.

Since ReScript is derived from ReasonML which has been around longer, searching for resources there might turn out more fruitful. The first search result gave me this text, which is also a chapter from an online book (which I haven’t read, so I don’t know about the quality): Functors (advanced) • Exploring ReasonML

2 Likes
3

Something additional to keep in mind is that OCaml tends to use functors much more than ReScript does. The reason is that the generated code is difficult to optimize, which is especially a problem when compiling to JavaScript. The OCaml stdlib Map, for example, uses a functor to generate all of the Map functions, whereas the Belt.Map does not.

As to why functors are necessary for maps, sets, etc, it’s related to type safety and the fact that functors are one of the few ways we can dynamically create new types.

To use Belt.Map as the example, you’ll notice that its type is defined like this: Belt.Map.t<'key, 'value, 'identity>. The key and value parameters are probably obvious since they correspond to how we normally think about maps (in the example posted above, key = int and value = string).

The problem is that it’s actually possible to create different maps that have the same key and value types but are implemented differently. Internally, Belt.Map uses the cmp function to organize its keys. From a type system perspective, these following functions are identical even though they do different things:

let cmp1 = (a, b) => compare(a, b)
let cmp2 = (a, b) => compare(b, a)

We need a way to express that different implementation in the type system, which is what the identity type parameter does.

The MakeComparable functor creates a unique identity type to solve the problem for us. What happens if you try to merge two maps that sort their keys completely differently? With Belt’s implementation, you receive a type error.

Example code 
module IntCmp1 = Belt.Id.MakeComparable({
  type t = int
  let cmp = (a: t, b: t) => compare(a, b)
})
module IntCmp2 = Belt.Id.MakeComparable({
  type t = int
  let cmp = (a: t, b: t) => compare(b, a) // This is different!
})
let m1 = Belt.Map.fromArray(~id=module(IntCmp1), [(1, "a"), (2, "b")])
let m2 = Belt.Map.fromArray(~id=module(IntCmp2), [(3, "c"), (4, "d")])
let m3 = Belt.Map.merge(m1, m2 /* <- This is an error! */, (_k, v1, v2) =>
  switch (v1, v2) {
  | (x, None) | (_, x) => x
  }
)

Triggers this error message:

This has type:
    Belt.Map.t<IntCmp2.t, string, IntCmp2.identity> (defined as
      Belt_Map.t<IntCmp2.t, string, IntCmp2.identity>)
  Somewhere wanted:
    Belt.Map.t<IntCmp1.t, string, IntCmp1.identity> (defined as
      Belt_Map.t<IntCmp1.t, string, IntCmp1.identity>)
  
  The incompatible parts:
    IntCmp2.identity vs IntCmp1.identity

All of this is why passing cmp as a simple callback function would not be sufficient. We need a way to “sign” the function with a unique type, which is where the functor system comes into play.

The OCaml stdlib Map works differently, but is ultimately based on the same idea. When you use the OCaml Map.Make functor, it also uses its input to create a new type. Different maps based on different input modules (and different compare functions) are incompatible.

4 Likes