Typescript: Function composition and recurrent types
While I was working on our toolkit library Desmond I stumbled upon a problem when defining the TypeScript definition for a function pipe
.
With help from Joe Calzaretta, a software developer working for MIT’s IS&T, I defined type definitions for a variadic function composition in TypeScript, that is in some aspects superior to the existing solutions implemented in popular libraries.
Adapting the proposed solution I managed to define the HOC function type for composition without overloads, ultimately allowing it to safely type-check function chain for any number of arguments, which is a feature lacking in type definitions of even extremely popular utility libraries such as Lodash.
What is pipe
?
Pipe
is a Higher-order variadic function, that performs a left-to-right function composition.
Here is an example of pipe
definition for two arguments.
const pipe = (f, g) => (input) => g(f(input));
What is Higher-order function?
Higher-order function (HOF) is a function that either:
- accepts a function as an argument
- returns a function
As you can see, the pipe
satisfies both arguments inherently.
What is a variadic function?
Variadic function is a function that accepts any number of arguments. In this case it practically means that pipe
can take a single argument, two arguments, etc. and perform the composition.
For non-variadic functions, we specify arity, which is the number of arguments (unary, n-ary etc).
Trivial pipe
example
Here is a short snippet of code that shows how pipe
works and what is to be expected of it.
const add = (a: number) => (b: number) => a + b;
const addConstants = pipe(add(5), add(7));
addConstants(0); // 0 + 5 + 7 = 12
addConstants(100); // 100 + 5 + 7 = 112
This example is banal and does not seem practically useful. However, function composition allows users to write a functional, modular code. We practically use it every day in back-end development for composing middleware handlers.
At this point, you might wonder, why don’t we use an existing implementation, such as Lodash’s flow or Ramda’s pipe, both of which would work well for the provided trivial example. But Desmond’s pipe
does more than that.
It handles asynchronous code via promises or async functions and provides a uniform (promise) interface.
Desmond’s pipe specification
- Create a function as left-to-right composition of arguments (arguments are functions)
- First functional argument can be of any arity, while the remaining function must be unary (in JavaScript, a function can return only a single value)
- Signature of the resulting (composed) function has argument(s) of the first function, and return type of the promise of the return type of the last function (even when all or some functions are synchronous)
- Each function in the chain always gets resolved value of the last return. If the previous function returns an array of promises, they are resolved via
Promise.all
before proceeding.
Hold on, that function already exists
The closest we got to an existing implementation is Ramda’s pipeP.
It does almost the same thing, but
- It fails if the argument of the first function is a promise
- It does not resolve arrays via
Promise.all
- Typescript typings are poor (Typescript typings favour OOP and FP typings are rarely correctly implemented)
Implementation
The implementation of pipe
is fairly short and consists of no more than 8 lines of code (one of which is a comment). You can check it out on GitHub.
It is conscious, readable and does all we wanted from it. The problem is not the execution logic, but the type definition of this function in TypeScript.
Compare the 8 lines of code to 50 lines of type definitions using overloads, which I wrote for the initial release of pipe
in Desmond 0.3.0
That ratio is insane, and the typing were not even complete.
The type problem
What is so challenging about the type of the pipe
function is the correct chaining of the functions. With the correct typing for the function, the user expects the following features.
1. Notify when the chain is broken
When user breaks the contract of the function chain, TypeScript should trigger an error:
pipe(
() => 21,
(n: number) => n * 2,
(n: string) => n.repeat(5), // Error: number is not assignable to string
);
2. Infer the argument type in chain
The function type should be inferred as the type of the function argument in pipe, based on the previous function return type.
pipe(
() => 21,
(n: number) => n * 2,
n => { /* let n: number */ }, // (inferred from previous return)
);
3. Have the correct type of the result
const meaning = pipe(
() => 21,
(n: number) => n * 2,
(n: number) => 'Answer: ' + n,
);
// const meaning: () => string
Having this solution for simple function composition without the async features, more or less gives us the solution for our pipe
. For simplicity let us assume, we want to achieve this for simple function composition, with the same interface and behavior as mentioned Lodash or Ramda functions.
Lodash and Ramda types
Do not reinvent the wheel. Lodash and Ramda have TypeScript type definitions, so I looked them up. See for yourself, here are the definitions for Ramda pipe and Lodash flow.
In both cases, typings are approached by overloads, which is a standard solution to the types too complex for TypeScript type definition language.
How is overloading useful here? TypeScript can (with relative ease) express pipe
function for a given number of composed functions and arity using template arguments.
See this commented snippet with definition for arity of two and two functions in the chain:
// A1, A2 -- first function arguments
// R1 -- first function return
// R2 -- second function return
// (a1: A1, a2: A2) => R1 -- first function
// (a: R1) => R2 -- second function
// (a1: A1, a2: A2) => R2 -- result function
pipe<A1, A2, R1, R2>(f1: (a1: A1, a2: A2) => R1, f2: (a: R1) => R2): (a1: A1, a2: A2) => R2;
Since this is possible, we can use overloads and define one for each possible case. That is obviously a lie, we cannot. There is infinitely many of them. But both Ramda and Lodash do it and it somewhat works, because they cover the most common uses.
But it is wrong. Here are several reasons:
- Type definitions are huge (sometimes even several times larger than the implementation)
- Types unmaintainable and pain to read or write
- Types are incomplete. Sure you might argue that nobody has a function of arity larger than… what? Five seems reasonable ceiling. But should the types be updated when someone has a function with six arguments?
NameLoCLoC TypesMax functionsMax arityLodash534974Ramda94566
For a summary, here is a short preview of Lodash and Ramda discussed functions. The you can compare the lines of code of the implementation and the types. Max functions (number of pipe arguments) and arity (number of arguments for the pipe’s first arguments) show how deep do the overloads go.
(Lines of code are informative, both libraries use custom types for definition and helpers for implementation, this is a rough approximation)
The types are incomplete and reach out to the size of five times larger than the implementation in case of Ramda.
Intuitive recurrent types
I don’t want to write lengthly type definitions that inherently cannot generally work. I want to write conscious, precise and elegant definitions. Not ones that could be generated by a script.
Using overloads in this example in TypeScript is like not having meta-programming at all. It is same like not using template arguments in types and defining all possible options with inlined argument types. With overloads. That’s how bad it is. We just don’t see it, because we have gotten used to it.
I despised the idea to the extent I tried to write the definition without overloads. For simplicity, all functions are unary, including the first one (extending the arity without overloads not an issue, as I will discuss another time).
type Chain<In, Out = In, Tmp = any> = []
| [(arg: In) => Out]
| [
(arg: In) => Tmp,
...Chain<Tmp, Out>
];
declare function flow<In, Out>(...fns: Chain<In, Out>): Out
Is it not beautiful? This type is a truly variadic function, it has no limits in number of arguments. It type-checks the function chain, matching outputs to inputs.
There is a single flaw to it. It does not compile since it is not a valid TypeScript type definition.
Compilation errors
Type alias 'Chain' circularly references itself.
This is the core issue. Recursion in TypeScript types is allowed only in some cases with interfaces, using a middleman type. This shall be discussed further, but for proof, see the cheesy example.
A rest element type must be an array type.
Another lesser issue is tuple types are not allowed to be spread at the moment. There is a proposal for that support however. (While writing this article, the mentioned issue had been fixed, the error still persists probably not because Chain
does not conform to Array
, but because its definition is corrupted due to the previous error and evaluated.)
Getting help
I am no TypeScript guru, at the time I did not even fully understand why Chain
is not an array type and why the second error even appeared in the compiler.
I tried to search for the related issues in TypeScript and discovered that almost every discussion even remotely related to word recursion splashes down to the argument about defining JSON structure in TypeScript, which is in this case completely irrelevant.
In the end, I created a question on StackOverflow. To my pleasant surprise, to this day there is no reference to JSON structure type in the thread.
Joe Calzaretta gave me in his answer type definition of the flow function. Here it is (unedited):
type Lookup<T, K extends keyof any, Else=never> = K extends keyof T ? T[K] : Else
type Tail<T extends any[]> =
((...t: T) => void) extends ((x: any, ...u: infer U) => void) ? U : never;
type Func1 = (arg: any) => any;
type ArgType<F, Else=never> = F extends (arg: infer A) => any ? A : Else;
type AsChain<F extends [Func1, ...Func1[]], G extends Func1[]= Tail<F>> =
{ [K in keyof F]: (arg: ArgType<F[K]>) => ArgType<Lookup<G, K, any>, any> };
type LastIndexOf<T extends any[]> =
((...x: T) => void) extends ((y: any, ...z: infer U) => void)
? U['length'] : neverdeclare function flow<F extends [(arg: any) => any, ...Array<(arg: any) => any>]>(
...f: F & AsChain<F>
): (arg: ArgType<F[0]>) => ReturnType<F[LastIndexOf<F>]>;
It has it’s drawbacks. It is relatively complex and has a parade of tough meta types that you need to fight through. The definition is all but conscious or elegant. It looks ugly, but it works!
Let us see how it stands to our expectations.
How it holds up
1. Notify when chain is broken
flow(
(n: number) => n * 2, // Type 'string' is not assignable to type 'boolean'.
(n: number) => 'Answer: ' + n,
(res: boolean) => res + '!',
);
The validation works, but is at the wrong line. This is actually a bug in TypeScript error messages. I started poking around it and Joe created an issue #28505 in TypeScript itself and it is now set on TypeScript 3.3 milestone.
2. Infer argument type in chain
flow(
(n: number) => n * 2,
n => { /* let n: any */ }, // (NOT inferred from previous return)
);
This is unfortunately a drawback of this solution. It is caused by the imperative validation type definition suggested by Joe, rather than my proposed recursively constructive solution (which is at this time invalid Typescript code).
3. Have correct type of the result
Result type inference works as expected:
const foo = flow(
(n: number) => n * 2,
(n: number) => 'Answer: ' + n,
(res) => res + '!',
);
// const foo: (arg: number) => string
Why are recurrent types forbidden?
An excellent question. As it appears from the Design Meeting Notes, 9/14/2018 (section Recursive Types), recursive types are not likely to be supported in the near future. The main argument against it, is an uncontrollable computationally intensive reference resolution.
Summary
With help from Joe Calzaretta, I managed to implement type definition for pipe
that handles n-ary first functions and any number of arguments. At this point, we can proudly add Desmond to the existing table, having very brief type definition, and unseen argument dynamics, even though suffering the type inference in the function chain.
You can see the implementation for yourself at GitHub.
Next time I might show you how to handle arity and explain the Joe’s solution step-by-step, because it is fascinating!