Changing mental model from typeclasses to modules and functors

1

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:

module ArrayOrderedSet: OrderedSet = {
  // ???

  type set<'t> = array<'t>
}

Here’s where my mental mapping from typeclasses to modules fails as I can’t see a way to link the 't of set<'t> to the t in the Ord module type.

Which makes me think there must be a more idiomatic ReScript-y way of doing this kind of thing with polymorphism and polymorphic constraints.

Any advice much appreciated.

2

Two suggestions:

  1. 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.

  2. 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)
3 Likes
3

Thanks for outlining a more idiomatic ReScript approach. Are there ReScript libraries that are considered good examples of these techniques in use?

4

with this with type in the return module annotation, will we see type element in IntSet as int or will be opaque?

5

FWIW, I found this description of first class modules: How to use the first class module in rescript? - #6 by johnj

6

Couple of points here.

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.

1 Like
7

Thanks – much appreciated.

1 Like
8

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.

Here’s the source code for Belt.Set (in OCaml, unfortunately): rescript-compiler/belt_Set.ml at master · rescript-lang/rescript-compiler · GitHub

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.

2 Likes
9

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.

4 Likes