Type Classes in ReasonML: A World of Functions for Free
Tags: reason, functional, ocaml
Published: 2019-12-12 03:45:30

Let's talk about type classes! *Eyes glaze over.* A senior developer can be heard grumbling, "I've been writing code for 20 years and not once have I needed to know what a monad is." Fresh out of coding bootcamp, a new team member [fires up Wikipedia](https://en.wikipedia.org/wiki/Type_class) and tries to make sense of the concept as it relates to "ad-hoc polymorphism in Haskell."

Clearly, these are topics for academics to theorize about, while the rest of us focus on getting _real work_ done.

## What _is_ a Type Class?

In reality, the goal of type classes is simply to identify (and name) patterns that exist among types. Intuitively, a `list('a)` seems to be more similar to `array('a)` than it is to a `bool`. If we can distill those similarities and write new functions built on top of the similar parts, we can avoid re-writing the same functions for both `list` and `array`, for example. 

And sure, sometimes the names used in functional programming can sound a little funny, but having a common vocabulary is useful!

It would be strange for a biologist to avoid funny words like "reptile", instead preferring to just talk about "snakes" and "alligators", or "cold-blooded-egg-layers" if they really need to generalize. Yet that's a bit what it sounds like when OCamlers proudly declare that [the language "doesn't bother you with monads everywhere"](https://www.slant.co/topics/15430/viewpoints/11/sections/1/history).

Of _course_ you can be a productive programmer without identifying these patterns, but when has finding patterns ever hurt? Learning to recognize them can have very practical benefits in real-life code. Building on top of established patterns allows you to write fewer functions, while gaining access to tons of well-tested "functions for free." For example:

- If you can put values of some type in order, you automatically gain the ability to "clamp" a value between some minimum and maximum
- Joining a `list(string)` is the same function as calculating the sum of an `array(int)`
- `array(option('a)) => option(array('a))` is the same as `list(promise('a)) => promise(list('a))`

In each of these cases, you only have to write one or two "foundational" functions, and in return you get access to a whole world of extra functions, just waiting to be used.

While I don't plan on covering all of those examples in depth, I'll definitely cover a few, and hopefully explain the techniques well enough that you end up with the tools necessary to dig into the more advanced examples. But first...

## A Refresher on Reason Modules

For the techniques described here to make sense, you'll need at least a passing familiarity with [modules in Reason](https://reasonml.github.io/docs/en/module).

At a high level:

- Every Reason file is a module, but (sub-) modules can also be defined using the `module` keyword.
- Every module has a type. This type is often inferred, but you can annotate [and even name](https://reasonml.github.io/docs/en/module#creation-1) module types.
- Modules [can include the contents of other modules](https://reasonml.github.io/docs/en/module#extending-module-signatures). Similarly, module _types_ can include other module types.
- Modules can be constructed by [taking other modules as parameters](https://reasonml.github.io/docs/en/module#module-functions-functors). These module-level functions are called "functors" in OCaml-speak, but I'll refer to them as "module functions" to avoid [ambiguity with a different "functor" concept](https://cs.stackexchange.com/questions/9769/what-is-the-relation-between-functors-in-sml-and-category-theory).

If some or all of that makes sense, you're ready for the rest of the post. That last bullet point in particular may seem odd, but hopefully through the examples presented here, the value will start to make sense.

## Building a Type Class: EQ

As mentioned above, type classes aim to represent things that different types have in common. A simple but concrete example of this: many types have the ability to compare values for equality. We can express this as a `module type` in Reason:

```reasonml
module type EQ = {
  type t;
  let equals: (t, t) => bool;
};
```

This module type definition doesn't _do_ anything, but it says "for a module to be a member of EQ, it should define some type and provide a function named `equals` that takes two values of that type and returns a boolean." We can provide a few concrete implementations of this module type:

```reasonml
module StringEq: EQ with type t = string = {
  type t = string;
  let equals = (a: string, b: string) => a == b;
};

module IntEq: EQ with type t = int = {
  type t = int;
  let equals = (a: int, b: int) => a == b;
};
```

A few quick notes about syntax:

- Using uppercase for the name of the module type isn't required; it's just a stylistic choice consistent with libraries like [bs-abstract](https://github.com/Risto-Stevcev/bs-abstract) and [ocaml-cats](https://github.com/bassjacob/ocaml-cats).
- The `with type t = ...` part of the signature is syntax for giving the outside world a hint about what types exist inside the module, since the `EQ` signature itself doesn't know anything about the `type t`. [This Github issue](https://github.com/reazen/relude/issues/193) covers the topic in more detail.

At this point, you'd be forgiven for not seeing how you get anything "for free" from this, so let's push ahead into a slightly fancier example.

## Extending EQ: ORD

Comparing values for equality is great, but what if we could put them in order? Enter the `ORD` type class, which is built on top of `EQ`:

```reasonml
module type ORD = {
  include EQ;
  let lte: (t, t) => bool;
};
```

This says that if you want to implement `ORD`, you need everything that `EQ` has (so, a type `t` and an `equals` function), plus you should also provide a "less than or equal to" function named `lte`. Note: this definition of `ORD` matches the [Fantasy Land spec](https://github.com/fantasyland/fantasy-land#ord). It's slightly different from the definition used by [PureScript](https://pursuit.purescript.org/packages/purescript-prelude/4.1.1/docs/Data.Ord#t:Ord) and [bs-abstract](https://github.com/Risto-Stevcev/bs-abstract/blob/v0.18.0/src/interfaces/Interface.re#L151), but they all accomplish the same thing.

We can again provide an implementation of this module type:

```reasonml
module IntOrd: ORD with type t = int = {
  include IntEq;
  let lte = (a: int, b: int): bool => a <= b;
};
```

With `ORD`, we finally start to get some functions for free! For example, you can imagine how if we have both `equals` and `lte` at our disposal, we can determine whether a value is "less than but not equal to" or "greater than" another value.

We implement this using module functions, effectively saying "if you can give me an `ORD` module, I can give you back all of these great _extra_ functions:

```reasonml
module OrdExtras = (Ord: ORD) => {
  let lt = (a, b) => Ord.lte(a, b) && !Ord.equals(a, b);
  let gt = (a, b) => !Ord.lte(a, b);
  let gte = (a, b) => gt(a, b) || Ord.equals(a, b);

  /**
   * Determine whether a value is between (inclusive) a provided min and max
   */
  let inRange = (~min: Ord.t, ~max: Ord.t, value: Ord.t): bool =>
    gte(value, min) && Ord.lte(value, max);

  /**
   * Clamp a provided value between (inclusive) a provided min and max
   */
  let clamp = (~min: Ord.t, ~max: Ord.t, value: Ord.t): Ord.t =>
    if (lt(value, min)) {
      min;
    } else if (gt(value, max)) {
      max;
    } else {
      value;
    };
};
```

Here, the extra functions don't know anything about the details of the type, they simply know that `equals` and `lte` are available to them, and additional functions can be built from those two.

Now we can construct this "extras" module with our `ORD` instance for `int` and use any of these functions with ints:

```reasonml
module IntOrdExtras = OrdExtras(IntOrd);

IntOrdExtras.clamp(~min=4, ~max=12, 1); /* 4 */
```

This _really_ starts to become valuable when we define our own types:

```reasonml
type month = Jan | Feb | Mar | Apr | ...;

/* By converting months to ints, we can easily rank them: */
let toInt = month =>
  switch (month) {
  | Jan => 0
  | Feb => 1
  | Mar => 2
  | Apr => 3
  | ...
  };

/* We can implement the ORD module type for our `month` type */
module MonthOrd: ORD with type t = month = {
  type t = month;
  let equals = (a: month, b: month) => a == b;
  let lte = (a, b) => IntOrd.lte(toInt(a), toInt(b));
};

/* ...which means we get all those extra functions, too */
module MonthOrdExtras = OrdExtras(MonthOrd);

/* now we can use functions like `clamp` and `inRange` with months */
MonthOrdExtras.inRange(~min=Feb, ~max=Apr, Mar); /* true */
```

## Type Class Laws

Now might be a good time to mention that while implementing type classes such as `EQ` and `ORD`, we relied on our intuition to "do the right thing" and provide sensible implementations. In reality, type classes come with "laws" that aren't generally represented in the type system, but can be tested for and should be obeyed.

For example, a lawful implementation of `ORD`'s `lte` function should obey the "transitive" property, meaning:

- if a <= b
- and b <= c
- then a <= c

These laws ensure that functions behave in a predictable way, even when used with completely different types. The [Fantasy Land Specification](https://github.com/fantasyland/fantasy-land) has definitions (including the laws!) for many common type classes.


## Semigroup and Monoid

`EQ` and `ORD` are relatively intuitive type classes (whose names are based on words that most English speakers will be familiar with). "Semigroup" and "Monoid" probably sound less familiar, but seeing a `module type` definition and an implementation might be enough to understand how they work:

```reasonml
module type SEMIGROUP = {
  type t;
  let concat: (t, t) => t;
};

module StringSemigroup: SEMIGROUP with type t = string = {
  type t = string;
  let concat = (a, b) => a ++ b;
};
```

`SEMIGROUP` applies to types where two values can be combined to produce a new value of the same type. Strings are an obvious candidate for inclusion, but ints would work too (twice, actually, one implementation using `+` to combine values, but another equally-valid implementation using `*`).

Here I've used the name `concat`, which will be familiar to JavaScript developers, but elsewhere in functional programming, this function is often named [append](https://pursuit.purescript.org/packages/purescript-prelude/4.1.1/docs/Data.Semigroup#v:append).

`MONOID` extends `SEMIGROUP` much like `ORD` extends `EQ`, in this case adding an empty value.

```reasonml
module type MONOID = {
  include SEMIGROUP;
  let empty: t;
};

module StringMonoid: MONOID with type t = string = {
  include StringSemigroup;
  let empty = "";
};
```

Semigroup and Monoid implementations also have laws to follow, for example:

- Semigroup is associative: `(a concat b) concat c` is the same as `a concat (b concat c)`
- The empty value is the identity: `(a concat empty) == a`

## ...And So Much More

There are also type classes for types that hold values of other types (such as `list('a)` and `option('a)`). [Andy White](https://github.com/andywhite37/) wrote some amazing in-depth articles on [types that can be mapped (called Functors)](https://andywhite.xyz/posts/2019-11-01-a-laymans-guide-to-functors-in-reasonml/) and [a type class built on top of `FUNCTOR` called `APPLICATIVE`](https://andywhite.xyz/posts/2019-11-07-a-laymans-guide-to-applicatives-in-reasonml/).

Some of the examples that I gave at the beginning (joining strings and turning a list-of-promises into a promise-of-a-list) are built around the Foldable type class (types that have a function similar to `reduce` for arrays in JavaScript). The functionality-for-free that comes from Foldable is so broad, I plan to devote an entire "part 2" post to it.

In the meantime, [I've created a Sketch](https://sketch.sh/s/bPVQRu00xmO7uYTQQHuCeX/) where you can play around with the type classes and implementations mentioned in this article. I hope you found it valuable. Let me know in the comments if anything was unclear!