Michael Martin-Smucker

Posted on Dec 12, 2019

Type Classes in ReasonML: A World of Functions for Free

#reason #functional #ocaml

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

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.

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 module types.
Modules can include the contents of other modules. Similarly, module types can include other module types.
Modules can be constructed by taking other modules as parameters. 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.

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:

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:

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 and 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 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:

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. It's slightly different from the definition used by PureScript and bs-abstract, but they all accomplish the same thing.

We can again provide an implementation of this module type:

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:

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:

module IntOrdExtras = OrdExtras(IntOrd);

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

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

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 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:

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.

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

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 wrote some amazing in-depth articles on types that can be mapped (called Functors) and a type class built on top of FUNCTOR called APPLICATIVE.

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 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!