Typescript Recursive Function Composition

Typescript recursive function composition

Circular type aliases are not really supported except in certain cases. (UPDATE TS 4.1, these are more supported now, but I'm still inclined to represent flow() as operating on AsChain that verifies a particular array of functions instead of trying to come up with a Chain that matches all valid arrays of functions)

Instead of trying to represent the specific type you've written there in a TypeScript-friendly way, I think I'll back up and interpret your question as: how can we type a flow()-like function, which takes as its arguments a variable number of one-argument functions, where each one-argument-function return type is the argument type for the next one-argument-function, like a chain... and which returns a one-argument function representing the collapsed chain?

I've got something that I believe works, but it's quite complicated, using a lot of conditional types, tuple spreads, and mapped tuples. Here it is:

type Lookup<T, K extends keyof any, Else=never> = K extends keyof T ? T[K] : Else

type Tail<T extends any[]> = T extends [any, ...infer R] ? R : 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 Last<T extends any[]> = T extends [...infer F, infer L] ? L : never;
type LaxReturnType<F> = F extends (...args: any) => infer R ? R : never;

declare function flow<F extends [(arg: any) => any, ...Array<(arg: any) => any>]>(
  ...f: F & AsChain<F>
): (arg: ArgType<F[0]>) => LaxReturnType<Last<F>>;

Let's see if it works:

const stringToString = flow(
  (x: string) => x.length, 
  (y: number) => y + "!"
); // okay
const str = stringToString("hey"); // it's a string

const tooFewParams = flow(); // error

const badChain = flow(
  (x: number)=>"string", 
  (y: string)=>false, 
  (z: number)=>"oops"
); // error, boolean not assignable to number

Looks good to me.

---

I'm not sure if it's worth it to go through in painstaking detail about how the type definitions work, but I might as well explain how to use them:

• Lookup<T, K, Else> tries to return T[K] if it can, otherwise it returns Else. So Lookup<{a: string}, "a", number> is string, and Lookup<{a: string}, "b", number> is number.

• Tail<T> takes a tuple type T and returns a tuple with the first element removed. So Tail<["a","b","c"]> is ["b","c"].

• Func1 is just the type of a one-argument function.

• ArgType<F, Else> returns the argument type of F if it's a one-argument function, and Else otherwise. So ArgType<(x: string)=>number, boolean> is string, and ArgType<123, boolean> is boolean.

• AsChain<F> takes a tuple of one-argument functions and tries to turn it into a chain, by replacing the return type of each function in F with the argument type of the next function (and using any for the last one). If AsChain<F> is compatible with F, everything's good. If AsChain<F> is incompatible with F, then F is not a good chain. So, AsChain<[(x: string)=>number, (y:number)=>boolean]> is [(x: string)=>number, (y: number)=>any], which is good. But AsChain<[(x: string)=>number, (y: string)=>boolean]> is [(x: string)=>string, (y: string)=>any], which is not good.

• Last<T> takes a tuple and returns the last element, which we need to represent the return type of flow(). Last<["a","b","c"]> is "c".

• Finally, LaxReturnType<F> is just like ReturnType<F> but without a constraint on F.

---

Okay, hope that helps; good luck!

Playground link to code

Typescript recursive function composition

Circular type aliases are not really supported except in certain cases. (UPDATE TS 4.1, these are more supported now, but I'm still inclined to represent flow() as operating on AsChain that verifies a particular array of functions instead of trying to come up with a Chain that matches all valid arrays of functions)

Instead of trying to represent the specific type you've written there in a TypeScript-friendly way, I think I'll back up and interpret your question as: how can we type a flow()-like function, which takes as its arguments a variable number of one-argument functions, where each one-argument-function return type is the argument type for the next one-argument-function, like a chain... and which returns a one-argument function representing the collapsed chain?

I've got something that I believe works, but it's quite complicated, using a lot of conditional types, tuple spreads, and mapped tuples. Here it is:

type Lookup<T, K extends keyof any, Else=never> = K extends keyof T ? T[K] : Else

type Tail<T extends any[]> = T extends [any, ...infer R] ? R : 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 Last<T extends any[]> = T extends [...infer F, infer L] ? L : never;
type LaxReturnType<F> = F extends (...args: any) => infer R ? R : never;

declare function flow<F extends [(arg: any) => any, ...Array<(arg: any) => any>]>(
  ...f: F & AsChain<F>
): (arg: ArgType<F[0]>) => LaxReturnType<Last<F>>;

Let's see if it works:

const stringToString = flow(
  (x: string) => x.length, 
  (y: number) => y + "!"
); // okay
const str = stringToString("hey"); // it's a string

const tooFewParams = flow(); // error

const badChain = flow(
  (x: number)=>"string", 
  (y: string)=>false, 
  (z: number)=>"oops"
); // error, boolean not assignable to number

Looks good to me.

---

I'm not sure if it's worth it to go through in painstaking detail about how the type definitions work, but I might as well explain how to use them:

• Lookup<T, K, Else> tries to return T[K] if it can, otherwise it returns Else. So Lookup<{a: string}, "a", number> is string, and Lookup<{a: string}, "b", number> is number.

• Tail<T> takes a tuple type T and returns a tuple with the first element removed. So Tail<["a","b","c"]> is ["b","c"].

• Func1 is just the type of a one-argument function.

• ArgType<F, Else> returns the argument type of F if it's a one-argument function, and Else otherwise. So ArgType<(x: string)=>number, boolean> is string, and ArgType<123, boolean> is boolean.

• AsChain<F> takes a tuple of one-argument functions and tries to turn it into a chain, by replacing the return type of each function in F with the argument type of the next function (and using any for the last one). If AsChain<F> is compatible with F, everything's good. If AsChain<F> is incompatible with F, then F is not a good chain. So, AsChain<[(x: string)=>number, (y:number)=>boolean]> is [(x: string)=>number, (y: number)=>any], which is good. But AsChain<[(x: string)=>number, (y: string)=>boolean]> is [(x: string)=>string, (y: string)=>any], which is not good.

• Last<T> takes a tuple and returns the last element, which we need to represent the return type of flow(). Last<["a","b","c"]> is "c".

• Finally, LaxReturnType<F> is just like ReturnType<F> but without a constraint on F.

---

Okay, hope that helps; good luck!

Playground link to code

Can recursively variadic functions be typed in Typescript?

The big caveat here is that there's almost no chance TypeScript's compiler will be able to infer the types the way you want them to; you will probably quite often find yourself needing to either manually specify type parameters or even assert that a particular function is a generic one. TypeScript isn't Haskell, and it isn't trying to be (much).

That being said, here's one possible typing for variadic:

interface Variadic<T, U> {
  (x: T): Variadic<T, U>
  runVariadic: U,
}

const variadic = <T, U>(f: (args: T[]) => U) => {
  const go = (args: T[]): Variadic<T, U> =>
    Object.defineProperty(
      (arg: T) => go(args.concat([arg])),
      "runVariadic",
      { get: function () { return f(args) }, enumerable: true });

  return go([]);
}

The idea is that variadic's accepts a function taking an array of T and returning a U, and turns it into a Variadic<T, U>. A Variadic<T, U> is a function that takes a T argument and returns a Variadic<T, U>, and it also has a runVariadic property of type U.

---

Here's a short test:

const str = variadic((args: string[]) => args)("hey")("you")("guys").runVariadic; // string[]
console.log(str) // ["hey", "you", "guys"]

Here I'm passing variadic the id function which is annotated to take and return an array of strings. Then the resulting Variadic<string, string[]> can take any number of string arguments one after another, and finally its runVariadic property is inferred by the compiler to be a string[], as borne out by the console log.

---

For your test code, a lot of manual typing and asserting has to happen:

const arrFold = <T, U>(alg: (x: T) => (y: U) => T) => (zero: T) => (xs: U[]) =>
  xs.reduce((acc, x) => alg(acc)(x), zero);
const comp = <T, U>(f: (x: T) => U) => <V>(g: (x: V) => T) => (x: V) => f(g(x));
const id = <T>(x: T) => x;

const varComp = variadic(arrFold(comp)(id)) as
  Variadic<(x: number) => number, (x: number) => number>;

const inc = (x: number) => x + 1;

const main = varComp(inc)(inc)(inc)(inc)(inc);
console.log(
  main.runVariadic(0)); // 5

The typings of arrFold, comp and id are reasonably straightforward, but the resulting type of varComp as inferred by the compiler is riddled with unknowns. Instead I've asserted it to be Variadic<(x: number) => number, (x: number) => number>, since I know we will be passing inc to it. So main.runVariadic is inferred as (x: number) => number), which also looks good.

---

Okay, hope that gives you some direction. Good luck!

Playground link to code

Funciton composition in Typescript without overloads

There isn't a way to remove all the overloads. The way the type R* parameters depend on one another is not expressible in the type system currently.

One improvement we can make is to remove the need for overloads adding extra parameters on the first function (the ones that add the A* type parameters). This can be done in 3.0 using tuples in rest parameters

interface LoDashStatic {

    flow<A extends any[], R1, R2>(f1: (...a: A) => R1, f2: (a: R1) => R2): (...a: A) => R2;

    flow<A extends any[], R1, R2, R3>(f1: (...a: A) => R1, f2: (a: R1) => R2, f3: (a: R2) => R3): (...a: A) => R3;

    flow<A extends any[], R1, R2, R3, R4>(f1: (...a: A) => R1, f2: (a: R1) => R2, f3: (a: R2) => R3, f4: (a: R3) => R4): (...a: A) => R4;

    flow<A extends any[], R1, R2, R3, R4, R5>(f1: (...a: A) => R1, f2: (a: R1) => R2, f3: (a: R2) => R3, f4: (a: R3) => R4, f5: (a: R4) => R5): (...a: A) => R5;

    flow<A extends any[], R1, R2, R3, R4, R5, R6>(f1: (...a: A) => R1, f2: (a: R1) => R2, f3: (a: R2) => R3, f4: (a: R3) => R4, f5: (a: R4) => R5, f6: (a: R5) => R6): (...a: A) => R6;

    flow<A extends any[], R1, R2, R3, R4, R5, R6, R7>(f1: (...a: A) => R1, f2: (a: R1) => R2, f3: (a: R2) => R3, f4: (a: R3) => R4, f5: (a: R4) => R5, f6: (a: R5) => R6, f7: (a: R6) => R7): (...a: A) => R7;

}

declare const _: LoDashStatic;

let f = _.flow((n: number, s: string) => n + s, o => o.toUpperCase()); // f: (n: number, s: string) => string

Type tuple so that function chain has valid parameter and return types

Indexing into the next or previous value of a tuple given an index type K is something I'd do with the support for variadic tuple types. Consider Tail<T>, which takes a tuple type T and returns a new tuple type with the first element removed:

// Tail<[1,2,3]> is [2,3]
type Tail<T extends readonly any[]> = T extends [any, ...infer R] ? R : never;

Then "T[K+1]" can be expressed as Tail<T>[K] instead.

That's probably the answer to your question as asked, but I'll continue a little to show how to use it:

---

Here's how I might start writing your CheckFuncs type:

type CheckFuncs<T extends readonly ((x: any) => any)[]> = { [K in keyof T]:
    K extends keyof Tail<T> ? (
        [T[K], Tail<T>[K]] extends [(x: infer A) => infer R, (x: infer S) => any] ? (
            [R] extends [S] ? T[K] : (x: A) => S
        ) : never
    ) : T[K]
}

That walks through T and compares T[K] with Tail<T>[K], and converts T[K] into a version of itself that works. Then these (note that you need const assertions for the tuple type to be preserved):

const pass = [(a: string) => 1, (a: number) => 'A', (a: string) => 2] as const
const fail = [(a: string) => 1, (a: number) => 3, (a: string) => 2] as const

produce these:

type passType = CheckFuncs<typeof pass>
// readonly [(a: string) => number, (a: number) => string, (a: string) => number]

type failType = CheckFuncs<typeof fail>
// readonly [(a: string) => number, (x: number) => string, (a: string) => number]

And you can make a function that works with CheckFuncs like this:

function useFuncs<T extends readonly ((x: any) => any)[]>(...t: CheckFuncs<T>) { }

useFuncs((a: string) => 1, (a: number) => 'A', (a: string) => 2); // okay
useFuncs((a: string) => 1, (a: number) => 3, (a: string) => 2); // error!
// ----------------------> ~~~~~~~~~~~~~~~~
// Argument of type '(a: number) => number' is not assignable to 
// parameter of type '(x: number) => string'.

Of course the exact way you want to write or use CheckFuncs might be different; this is just an illustration. Hope that helps; good luck!

Link to code

---

Related Topics