Molten Matter

An introduction to typeclasses

The other day I found myself trying to explain what I liked about Ur/Web typeclasses and how they worked, and I realized that my comment would probably end up long enough to be a half decent post, so here I am.

The concept behind typeclasses is actually pretty simple, and it can be implemented in any language that supports generics and functions as arguments to other functions. Which is basically all modern languages (a category to which Go refuses to belong). Given a normal increase function:

const incr = (n) =>
  n + 1;

We can hoist the increment operation into the arguments to the function, letting us provide our own implementation.

const incr = (incrementor) => (n) =>
  incrementor(n);

incr(x => x + 1)(1)

The usefulness of this starts becoming clearer when you define more complex operations on top of of the basic ones:

const is_zero = (counter) => (n) => counter.is_zero(n);
const incr = (counter) => (n) => counter.incr(n);
const decr = (counter) => (n) => counter.decr(n);

const add = (counter) => (n, m) =>
  is_zero(counter)(m) ? n :
    add(counter)(incr(counter)(n), decr(counter)(m));

const counter = {
  is_zero: (n) => { return n === 0; },
  incr: (n) => { return n + 1; },
  decr: (n) => { return n - 1; }
};

add(counter)(1, 2);

The arguments to add don’t necessarily have to be numbers: they can be anything, as long as you provide a suitable implementation of counter.

const screamer = {
  is_zero: (s) => { return s.length === 0; },
  incr: (s) => { return s + "A"; },
  decr: (s) => { return s.slice(0, -1); }
};

add(screamer)("AA", "AAAAAA");

We could also write a generic json encoding function (I know these are awful JSON encoding functions, just bear with me for a moment):

const json_encode = (encoder) => (j) =>
  encoder(j);

const encode_string = (s) =>
  "\"" + s.replace("\"", "\\\"") + "\"";

const encode_int = (i) =>
  i.toString();

const encode_pair = (e1, e2) =>
  (p) =>
    "[" + e1(p[0]) + "," + e2(p[1]) + "]";

json_encode(encode_pair(encode_string, encode_int))
  (["The sun went down with practiced bravado.", 451]);

If you’ve ever used Elm, this might remind you of Json.Decode’s interface, which has you building up a decoder implementation function with the right type for your desired object out of smaller decoder functions.


Now imagine passing the implementation as the first argument to almost every function call in your codebase. Do you feel like gouging your eyes out yet? Fret not, for type classes are here to the rescue!

Type classes are more or less a mechanism for inferring the right implementation based on the type of the arguments, so you don’t have to write it explicitly. Some languages that implement them at language level are Haskell, Scala and Ur/Web. There’s an ongoing effort to embed type classes into OCaml in the form of modular implicits, but it seems to be progressing slowly.

Ur/Web’s implementation introduces a keyword, class, with which you can declare a constructor type that will be specially marked by the compiler, and lets you defined implementations as normal values:

(* counter.mli *)
class counter

val incr : t ::: Type -> counter t -> t -> t
val decr : t ::: Type -> counter t -> t -> t
val isZero : t ::: Type -> counter t -> t -> bool
val mkCounter : t ::: Type -> { Incr : t -> t, Decr : t -> t, IsZero : t -> bool } -> counter t

val counter_int : counter int
val counter_scream : counter string

(* counter.ml *)
con counter a = { Incr : a -> a
                , Decr : a -> a
                , IsZero : a -> bool }

fun mkCounter [a] (x : { Incr : a -> a, Decr : a -> a, IsZero : a -> bool }) =
  x

fun incr [a] (c : counter a) : a -> a = c.Incr
fun decr [a] (c : counter a) : a -> a = c.Decr
fun isZero [a] (c : counter a) : a -> bool = c.IsZero

val counter_int =
  mkCounter { Incr = fn x => x + 1
            , Decr = fn x => x - 1
            , IsZero = fn x => x = 0 }

val counter_scream =
  mkCounter { Incr = fn x => x ^ "A"
            , Decr = fn x => substring x 0 ((strlen x) - 1)
            , IsZero = fn x => x = "" }

Registering a function as a possible implementation for a typeclass is just a matter of calling it with a properly typed function. Now we can use incr, decr and isZero freely on the types we have provided an implementation for without specifying the implementations explicitly.

incr 1
=> 2

decr "AAA"
=> "AA"

isZero True
(* will not compile *)

We can provide multiple implementations for any given type, and Ur/Web will choose the last one we have registered. Since typeclass implementations here are just normal values, only typeclass implementations that are currently in scope will be available, and if we want to force a specific implementation we can pass it explicitly.

incr [some_counter_implementation] 1
=> 2

Haskell’s typeclasses work a little differently: typeclasses are not quite like normal types, and there’s a special syntax for defining implementations, here called instances, of a particular class. The compiler does not attempt any sort of instance resolution and will complain if it finds more than one implementation of a particular typeclass in the same program. This leads to a few annoyances, because a library is not allowed to define its own private implementation of a typeclass without polluting the global namespace. This is usually solved by using newtypes, which is kind of unwieldy.

I don’t know Scala, but its type classes are called “implicits” and they seem to be similar to Ur/Web’s, save for not supporting multiple implementations in scope.

OCaml’s modular implicits are a lot like Ur/Web’s, but their use is constrained to modules rather than any kind of value. As in Ur/Web, there’s a special syntax for forcing a specific implementation for a certain type to be used, but unlike Ur/Web and as in Scala only one implicit module is allowed in scope. It’s also possible to use a non-implicit module as implementation by passing it explicitly, so even if there is an implicit module already in scope it’s easy to override it.


Further reading:

#np Animals as Leaders - The Future That Awaited Me