Higher-kinded polymorphism with JavaScript and Flow, in depth

This is part two of a series. Part one explains what higher-kinded polymorphism is, and the errors that occur when you try to use it in Flow.

This post is based on gcanti’s original post on implementing higher-kinded types in Flow, which is itself based on Yallop & White. It also draws heavily from the implementation of these concepts in flow-static-land. These sources assume a certain level of familiarity with type systems which can make jumping in and using these concepts and this library difficult for newcomers, so this post aims to be an introduction for those with no prior experience with functional programming or advanced type systems.

Brief diversion: functors

As a motivating example, we are going to make our BinaryTree from part one into a Functor. Functor is a higher-kinded abstraction, very commonly used in functional programs, which represents anything with a map function. (Yes, this is basically the same map that you are used to seeing on arrays.) Here is an interface for Functor:

interface Functor<F> {
  map<A, B>(fn: (a: A) => B, fa: F<A>): F<B>;
}

(keep in mind that this is not valid flow code, because it is trying to use a generic argument to abstract over the higher-kinded type F)

A Functor can be thought of like a box that holds a value, and its map function allows us to transform the value that’s inside of that box. For instance, I can turn an Array<string> to an Array<number> by mapping it with the function str => str.length. The generics A and B don’t have to be different types; we can go from Array<number> to Array<number> with all sorts of functions, like x => x * x to square all of the numbers in an array. Many things which we work with have natural implementations as functors: arrays, sets, maps, trees. Even promises can be seen as a functor, in which case map applies a function to the value which the promise will eventually return. It’s a useful interface for us to implement.

(For a type to be a functor, its map function must also follow certain restrictions, known as “the functor laws”. I’ve written a more thorough introduction to functors here.)

Defining map in an acceptable way

The first and most important step in creating a functor is side-stepping the fact that our map definition is invalid, because a generic cannot be passed as a parameter to another generic. To do so, we will create a type that represents the idea of passing a type to a generic. We’ll call this type HKT, for “higher-kinded type”, and define it as follows:

// Code taken from flow-static-land
class HKT<F, A> {}

This is exactly what it looks like: a class which takes two type parameters, but which has absolutely no implementation. This type serves the purpose of representing the application of the type parameter A to the type constructor F. We can think of it like this: HTK<F, A> = F<A>.

With HTK in hand, we can now define our Functor interface in a way which Flow accepts:

// Code taken from flow-static-land
interface Functor<F> {
  map<A, B>(f: (a: A) => B, fa: HKT<F, A>): HKT<F, B>;
}

Mentally substituting F<A> for HKT<F, A>, and F<B> for HKT<F, B>, we can see that this is equivalent to the definition of Functor given in the previous section.

The next step is exporting a type which is compatible with this signature. We define this as a type alias for HKT, so callers which refer to our type constructor directly can use the nice type BinaryTree<A>, but generic code can treat our type as an instance of HKT.

export type BinaryTree<A> = HKT<?, A>;

Here’s the question though: what goes in place of the ?? We need something unique to our data structure, because other types will also be defined as HKT<?, A>, and we need the value of ? to be different in each case to make sure the types are distinct. Also, just as HKT represents the idea of applying a type parameter to a type constructor, but doesn’t actually do it, we only need to make this unique value represent the idea of “being a binary tree”, not actually be one. The solution, then, is just as minimal as our definition of HKT was:

class IsBinaryTree {}
export type BinaryTree<A> = HKT<IsBinaryTree, A>;

This IsBinaryTree class is called a “brand”. In the parlance of the paper, it is an “uninhabited opaque type” — uninhabited meaning that we will never construct an instance of it, opaque meaning that we will never look inside of it. The purpose of a brand is solely to differentiate one higher-kinded type from another, and every type constructor which we want to use polymorphically must have its own brand.

So now we have a definition of Functor and BinaryTree which can be used how we want them to. How do we write an implementation of a BinaryTree, given these new representations?

Implementing BinaryTree, again

We are going to separate our data structure into an internal representation and an external interface. Our implementation is the same as it was in part one, but instead of calling our type BinaryTree<A> (the name of our exported type constructed with HTK and our brand) we’ll call it BinaryTreeI<A>, where the “I” stands for “internal”.

export class BinaryTreeNode<A> {
  left: BinaryTreeI<A>;
  right: BinaryTreeI<A>;
  constructor(left: BinaryTreeI<A>, right: BinaryTreeI<A>) {
    this.left = left;
    this.right = right;
  }
}
export class BinaryTreeLeaf<A> {
  value: A;
  constructor(value: A) {
    this.value = value;
  }
}
type BinaryTreeI<A> = BinaryTreeNode<A> | BinaryTreeLeaf<A>;

We will implement an internal version of the map function which is polymorphic on A, but which only operates on BinaryTree rather than being generic in the functor it accepts. This is a straightforward recursive function, which applies its function argument to each leaf node in the tree.

function mapBinaryTree<A, B>(fn: (a: A) => B, tree: BinaryTreeI<A>) : BinaryTreeI<B> {
  if (tree instanceof BinaryTreeNode) {
    return new BinaryTreeNode(
      mapBinaryTree(fn, tree.left),
      mapBinaryTree(fn, tree.right));
  }
  return new BinaryTreeLeaf(fn(tree.value));
}

Connecting our internal implementation to its external representation

So we have a working internal implementation of a binary tree, and an external type signature of it which makes the typechecker happy. Let’s make a couple of functions to glue them together:

export function inj<A>(a: BinaryTreeI<A>): BinaryTree<A> {
  // ?
}
export function prj<A>(fa: BinaryTree<A>): BinaryTreeI<A> {
  // ?
}

inj stands for “inject”, and is what we will use to shove our real implementation of a binary tree into the representation used by the outside world. prj stands for “project”, and is what we will use to unpack the external representation into a real implementation that we can work with.

Remember that BinaryTree<A> is just a representation of a higher-kinded type, and that nothing will look inside of its structure, and the implementation of these two functions becomes easy: they’re just unsafe type coercions, which return their argument unchanged.

export function inj<A>(a: BinaryTreeI<A>): BinaryTree<A> {
  return ((a: any): BinaryTree<A>)
}
export function prj<A>(fa: BinaryTree<A>): BinaryTreeI<A> {
  return ((fa: any): BinaryTreeI<A>)
}

This may seem concerning at first, but as long as we never use unsafe casts outside of these two functions, we do not actually sacrifice any type safety by doing this. Any instance of BinaryTree<A> which our program encounters will be created by inj, and the signature of inj declares its argument as BinaryTreeI. This means that the only things which can be cast to BinaryTree<A> are valid instances of BinaryTreeI<A>. Similarly, prj declares that its input type is of BinaryTree<A>. Since we know that every BinaryTree<A> is a valid BinaryTreeI<A>, the unpacking operation will always be safe.

Now, all that’s left is to implement map using mapBinaryTree, inj, and prj.

export function map<A, B>(f: (a: A) => B, fa: BinaryTree<A>): BinaryTree<B> {
  return inj(mapBinaryTree(f, prj(fa)));
}

We project our BinaryTree<A> to a BinaryTreeI<A> before using it, and then inject the result back into a BinaryTree<A> before returning it.

A note on inj and prj: in this case, it’s possible to change our implementations to make a definition of BinaryTree that does not rely on them, in which the real, recursive data type is exported. What inj and prj win us is a separation of concerns. With them, implementing a higher-kinded type is formulaic, done by implementing a type, implementing a signature, and binding them together. Without inj and prj, the method of implementing a higher-kinded type will vary from type, and the type’s internal implementation will tend to become messy due to the constraints of the higher-kinded concerns.

Tying it all up

Remember the type signature of Functor from flow-static-land:

interface Functor<F> {
  map<A, B>(f: (a: A) => B, fa: HKT<F, A>): HKT<F, B>;
}

We can use this and our brand to have the type system check that we’ve properly implemented Functor for our type:

if (false) {
  ({map} : Functor<IsBinaryTree>)
}

This just says that an object containing our map function can be cast to an instance of Functor, marked by the brand for our type constructor. The whole thing is wrapped in an if (false) { ... } to ensure that the typechecker sees it, but running code will not.

We can also test how this code will be called in practice:

function doubleContents<F, A>(fa: HKT<F, A>, functor: Functor<F>) : HKT<F, [A, A]> {
  return functor.map(x => [x, x], fa);
}
const numberTree =
  new BinaryTreeNode(
    new BinaryTreeNode(
      new BinaryTreeLeaf(1),
      new BinaryTreeLeaf(2)),
    new BinaryTreeNode(
      new BinaryTreeLeaf(3),
      new BinaryTreeLeaf(4)
    ));
console.dir(doubleContents(numberTree, {map}), { depth: null })

As in part one, this is not a particularly useful function, but was chosen for simplicity’s sake.

doubleContents uses HKT<F,A> rather than F<A> in its type signature. It also takes an object conforming to the Functor interface. Our result is a generic form of a function which takes any functor, and replaces each item inside of it with a tuple of that item and itself:

BinaryTreeNode {
  left: BinaryTreeNode {
    left: BinaryTreeLeaf { value: [ 1, 1 ] },
    right: BinaryTreeLeaf { value: [ 2, 2 ] } },
  right: BinaryTreeNode {
    left: BinaryTreeLeaf { value: [ 3, 3 ] },
    right: BinaryTreeLeaf { value: [ 4, 4 ] } } }

In conclusion

With a couple of tricks, we can make Flow’s type system much more powerful, enough to work with a host of useful, highly generic abstractions which are usually confined to specific languages. Functor is just one of these among many. If these abstractions are new to you, Functors, Applicatives, and Monads in Pictures provides a good explanation of some common ones. To get an idea of what sorts of abstractions are possible, check out the long list of them which flow-static-land implements. And if you want to a place to get started playing with these concepts in JavaScript, flow-static-land has a list of introductory exercises here.

Happy polymorphing!

The runnable code from this post may be found here.