What is higher-kinded polymorphism?
An Explanation in JavaScript and Flow
This post is part one of a series. It explains what higher-kinded polymorphism is, and the limitations Flow has in this area. Part two explains how to work around Flow’s limitations to use higher-kinded abstractions anyway.
If you’ve spent much time listening to functional programmers talk about their language preferences, you may have heard them reference “higher-kinded types” as a desirable feature of a functional language. It’s a tool that allows programmers to build powerful abstractions in languages like Haskell and PureScript, but it may seem foreign to developers who are used to languages without it, such as Java, C#, Elm, TypeScript, or Flow. This post aims to explain what higher-kinded types and higher-kinded polymorphism are in an accessible way, which assumes familiarity with JavaScript, Flow, and generics, but no experience with functional programming or strong type systems.
What is higher-kinded polymorphism, and why would I want it?
Before we look at higher-kinded polymorphism, let’s do a refresher on regular, parametric polymorphism, also known as generics.
A generic tree
To start, here’s a definition of a generic BinaryTree type, which represents a binary tree containing values of some other type:
class BinaryTreeNode<A> {
left: BinaryTree<A>;
right: BinaryTree<A>;
constructor(left: BinaryTree<A>, right: BinaryTree<A>) {
this.left = left;
this.right = right;
}
}class BinaryTreeLeaf<A> {
value: A;
constructor(value: A) {
this.value = value;
}
}type BinaryTree<A> = BinaryTreeNode<A> | BinaryTreeLeaf<A>;
Because this type is generic, I can define a function which operates upon the values it contains, regardless of what type those values are. In this case, I’ll write a function which replaces each leaf value with a tuple containing two copies of itself:
function doubleTree<A>(tree: BinaryTree<A>) : BinaryTree<[A, A]> {
return tree instanceof BinaryTreeLeaf ?
new BinaryTreeLeaf([tree.value, tree.value]) :
new BinaryTreeNode(doubleTree(tree.left),
doubleTree(tree.right));
}Now, we can construct and work with BinaryTrees which contain a variety of types:
const numberTree =
new BinaryTreeNode(
new BinaryTreeNode(
new BinaryTreeLeaf(1),
new BinaryTreeLeaf(2)),
new BinaryTreeNode(
new BinaryTreeLeaf(3),
new BinaryTreeLeaf(4)));console.log("number tree:");
console.dir(numberTree, { depth: null });
console.log("doubled number tree:");
console.dir(doubleTree(numberTree), { depth: null });
console.log("string tree:");
console.dir(doubleTree(new BinaryTreeLeaf("foo")), { depth: null });
The code’s output shows that things work as expected.
number tree:
BinaryTreeNode {
left: BinaryTreeNode {
left: BinaryTreeLeaf { value: 1 },
right: BinaryTreeLeaf { value: 2 } },
right: BinaryTreeNode {
left: BinaryTreeLeaf { value: 3 },
right: BinaryTreeLeaf { value: 4 } } }doubled number tree:
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 ] } } }string tree:
BinaryTreeLeaf { value: [ 'foo', 'foo' ] }
Generics, abstraction, and polymorphism
doubleTree is a polymorphic function. It can take data of many types, such as BinaryTree<number> or BinaryTree<string>, and work with any of them. This is the essence of generics: they allow us to abstract over the concrete types that we’re dealing with. We can write similar doubling functions for other types as well:
function doubleArray<A>(array: Array<A>) : Array<[A, A]> {
const newArray = [];
for (let i = 0; i < array.length; i++) {
newArray.push([array[i], array[i]]);
}
return newArray;
};Let’s look at the signature of these two functions side by side:
doubleTree<A>(BinaryTree<A>) : BinaryTree<[A, A]>
doubleArray<A>( Array<A>) : Array<[A, A]>The only difference between them is the parametric type: BinaryTree in one case, Array in the other. One could imagine us writing a generic function which works with any concrete doubling function, like the following.
type doubler<A, X> = (X<A>) => X<[A, A]>;function doubleSomething<A,X>(xa: X<A>, double: doubler) : X<[A, A]> {
return double(xa);
}doubleSomething(numberTree, doubleTree);
doubleSomething([1, 2, 3], doubleArray);
(yes, this function has minimal practical utility. More interesting and useful examples of this kind of generic programming are beyond the scope of this post)
Unfortunately, when we try to do this, Flow objects to the type declaration of doubler:
error| Incorrect number of type parameters (expected 0)This is saying that X, the generic argument declared with doubler<A, X> cannot be passed another generic argument in X<A>. The reason for this limitation is that Flow supports using generics to abstract over types, but it does not support using them to abstract over type constructors.
Types, type constructors, and kinds
To dig in to the difference between types and type constructors, consider our BinaryTree. We can make the argument to a function have the typeBinaryTree<number>, BinaryTree<string>, BinaryTree<Array<number>>, etc., but we could not make an argument have the type BinaryTree or BinaryTree<Array>. This is because things in the first list are fully specified types, whereas things in the second list are not. Trying to pass BinaryTree to a function raises the question, “a binary tree of what?”
This is the distinction between types, and type constructors. A type is something that your code can use on its own, but a type constructor has to take another type as a parameter, to produce a usable type. (This is why generic functions are also called “parametrically polymorphic”, because they’re polymorphic over type parameters)
In functional languages with very strong type systems, the distinction between types and type constructors is expressed using “kinds”. If you squint, you can sort of think of a kind as the “type of a type.” Kinds are defined like this:
* is the kind of every type. This includes number, string, Array<number>, BinaryTree<Array<string>>, BinaryTree<A> , Array<BinaryTree<A>>, etc. Absolutely any type that you could create a variable of.
* -> * is the kind of a type constructor which takes one type as a parameter. You can read this arrow as “something which takes a * and gives you a *.” BinaryTree has a kind of * -> *, as does Array, Set, and others.
Things of kind * -> * are sometimes called “unary type constructors”.
* -> * -> * is the kind of a type constructor which takes two types as parameters. It is something which takes a type, and then takes another type, and finally gives you a type. Map is an example; it needs to be constructed with two parameters, like Map<number, string>.
Things of kind * -> * -> * are sometimes called “binary type constructors”.
* -> * -> * -> * is the kind of a type constructor which takes three types as an argument… etc.
When we talk about “types”, we usually mean things with a kind of *. When we talk about “type constructors”, we usually mean things with a kind of * -> * or higher. Because of this, type constructors are also called “higher-kinded types”.
When a person says that a language “supports higher-kinded types”, what they mean is, that the language has first-class support for higher-kinded types, and lets you build abstractions over them in all of the same ways which you can abstract a type of kind *. The reason that this is important is that it increases the number and type of abstractions you can build; you may have heard of some of these which are common in typed functional programming and category theory, such as monoids, functors, applicatives, or monads. All of these are abstractions over certain properties of type constructors, and require higher-kinded types to make full use of.
Flow’s limitations on higher-kinded types
So know we know why Flow allows us to write a type signature like this:
type doubleArray<A> = (Array<A>) => Array<[A, A]>;but not a type signature like this:
type doubler<A, X> = (X<A>) => X<[A, A]>;In Flow, generic argument are restricted to having a kind of *. In these examples, A has the kind *, but X has the kind * -> *. Due to this, the second example is forbidden.
Once upon a time, this would have been the end of the story. Fortunately, there are nifty techniques which allow us to work with higher-kinded abstractions in languages which lack first-class support for them. We’ll see how to use these techniques in part two.
Code samples from this post, including all runnable examples, may be found here.
