# 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**.*