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 the help of Joe Calzaretta, a software developer working for MIT's IS&T, I defined type definitions for a variadic function composition in TypeScript, solution in some aspects superior to the existing implementations in popular libraries.

While 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 useful in practice. However, function composition allows users to write a functional, modular code. We 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

1. Create a function as left-to-right composition of arguments (arguments are functions)
2. 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)
3. 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)
4. 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

1. It fails if the argument of the first function is a promise
2. It does not resolve arrays via Promise.all
3. Typescript typings are poor (Typescript typings favour OOP and FP typings are rarely correctly implemented)

Implementation

The implementation ofpipe 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 ofpipe in Desmond 0.3.0 That ratio is insane, and the typing was 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 of 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. Inference of 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 ourpipe. For simplicity let us assume, we want to achieve this for simple function composition, with the same interface and behavior as in the above 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 handled 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(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 a pain to read or write
• Types are incomplete. Sure you might argue that nobody has a function of arity larger than... what? Five seems to be a reasonable limit. But should the types be updated when someone has a function with six arguments?

To sum up, here is a short preview of Lodash and Ramda discussed functions. 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 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 work in general. 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 the same like as using template arguments in types and defining all possible options with inline 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 that I tried to write the definition without overloads. For simplicity, all functions are unary, including the first one (extending the arity without overloads is not an issue, as I will discuss another time).

type Chain = []  
   | [(arg: In) => Out]  
   | [  
       (arg: In) => Tmp,  
       ...Chain   ];  
declare function flow(...fns: Chain): 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 = K extends keyof T ? T[K] : Else  
type Tail =   
 ((...t: T) => void) extends ((x: any, ...u: infer U) => void) ? U : never;  
type Func1 = (arg: any) => any;  
type ArgType = F extends (arg: infer A) => any ? A : Else;  
type AsChain> =  
 { [K in keyof F]: (arg: ArgType) => ArgType, any> };  
type LastIndexOf =  
 ((...x: T) => void) extends ((y: any, ...z: infer U) => void)  
 ? U['length'] : never  
  
declare function flow any, ...Array<(arg: any) => any>]>(  
 ...f: F & AsChain  
): (arg: ArgType) => ReturnType]>;

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 the help of 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!