I’m trying to transform my thinking from the Haskell world of typeclasses to the ReScript world of modules, module types and functors.

This may not be an ideal way to use ReScript but let’s assume I have module types for equality and ordering. I understand module inclusion is the idiomatic way to express the relationship between Eq and Ord:

module type Eq = {
type t
let eq: (t, t) => bool
}
module type Ord = {
include Eq
let cmp: (t, t) => int
}

Now I can create module instances for, say, integers:

module IntEq: Eq with type t = int = {
type t = int
let eq = \"=="
}
module IntOrd: Ord with type t = int = {
include IntEq
let cmp = Pervasives.compare
}

Now suppose I’d like to create a module type for ordered sets. I need to express the constraint that the elements of any ordered set must have an Ord module implementation:

module type OrderedSet = {
include Ord
type set<'t>
let empty: unit => set<'t>
let singleton: 't => set<'t>
let size: set<'t> => int
}

And an implementation using arrays would be handy:

Modules are structurally typed. You don’t need to create separate instance modules for your “type class” module signatures, and you don’t have to apply the module signature explicitly. If Int has t and eq defined according to Eq, it can be used directly where an Eq is expected.

Use first-class modules instead of functors. It allows you to pass a module as an explicit argument to a function, which is essentially how type class dictionaries are passed around, just implicitly.

However, if you insist on using a functor, you should understand that you can’t use a functor to apply a type parameter, because then it wouldn’t really be a type parameter anymore. Instead you need to add another type element, and use that as the "type parameter’:

module type OrderedSet = {
include Ord // This already includes a `type t`, so we don't need to also define `type set`
type element
let empty: unit => t
let singleton: element => t
let size: t => int
}
module ArrayOrderedSet = (T: Ord): (OrderedSet with type element = T.t) => {
type t = array<T.t>
type element = T.t
let empty = () => []
let singleton = x => [x]
let size = Array.length
let eq = failwith("TODO: use T.eq here")
let cmp = failwith("TODO: use T.cmp here")
}
module IntSet = ArrayOrderedSet(Int)

First, typically Eq would be derived from Ord, not the other way round, because given an ordering of a type, you can use that to derive whether values of the type are equal, but not the other way round:

module type Ord = {
type t
let cmp: (t, t) => int
}
module type Eq = {
include Ord
let eq: (t, t) => bool
}

Now given the above, there are a few ways to express the derivation relationship. But we should prefer the simplest, which is just a function:

let eqOfCmp = (cmp, t1, t2) => cmp(t1, t2) == 0

Now given any comparison function, we can derive an equality function from it. Let’s try it for a custom ‘rank’ type where the First rank is the highest, the Second is the middle, and the Third rank is the lowest:

module Rank = {
type t = First | Second | Third
let toInt = rank =>
switch rank {
| First => 3
| Second => 2
| Third => 1
}
let cmp = (t1, t2) => compare(toInt(t1), toInt(t2))
let eq = eqOfCmp(cmp)
}
// This proves that the Rank module really does conform to the Eq module type
module Test = (Inp: Eq) => {}
module T = Test(Rank)

‘Classically’ this has been done by using a functor. See the documentation of the OCaml Map module, for example. It’s available in ReScript too. That also answers the question of how to link the requirement that the set elements must be orderable.

Belt does this with its collections. Though it does so in a slightly more advanced way. Since passing the module explicitly to every function is a bit tedious, it does so only when the data structure is created and saves a reference to it (or rather directly to the functions it contains). It also includes a unique “id type” for the instance, to prevent data structures created with different instances operating on the same type to be used together.

Yes. It’s a type expression, so it can only affect the module type. It has no effect on the implementation. with type t = int makes t equal to int, while with type t := int substitutes t for int.

This is a good opportunity to also thank the ReScript community for their insightful answers to my questions and generally for creating a really impressive JS development environment.