Upon reviewing your inquiry, I interpret it as follows:

How can a TS type be assigned to this higher-order function in such a way that the type of x is allowed to vary throughout the loop?

function compose(...funs) {
    return function(x) {
        for (var i = funs.length - 1; i >= 0; i--) {
            x = funs[i](x);
        }
        return x;
    }
}

Unfortunately, directly typing this function is not possible. The issue lies with the funs array - for compose to have its most general type, funs should be a type-aligned list of functions where the output of each function matches the input of the next. TypeScript's arrays are homogeneously typed, requiring all elements of funs to have exactly the same type. This limitation prevents expressing the variance of types throughout the list in TypeScript. (The provided JS code operates at runtime due to type erasure and uniform data representation.) This is why Flow's $Compose serves as a special built-in type.

To address this limitation, one workaround is similar to what you've done in your example: declaring multiple overloads for compose with different numbers of parameters.

// Overload examples omitted for brevity

However, this approach is not scalable and may lead to issues when users need to compose more functions than anticipated.

Another approach involves rewriting the code so that only one function is composed at a time:

function compose<T, U, R>(g : (y : U) => R, f : (x : T) => U) : (x : T) => R {
    return x => f(g(x));
}

This modification complicates the calling code, necessitating repetition of the word compose and parentheses, proportionate to 'n'.

compose(f, compose(g, compose(h, k)))

In functional languages, function composition pipelines like these are common. To reduce syntactic discomfort, Scala introduces infix notation for functions like compose, leading to fewer nested parentheses.

f.compose(g).compose(h).compose(k)

Similarly, Haskell uses (.) instead of compose, resulting in concise function compositions:

f . g . h . k

It is feasible to create an infix compose in TypeScript through a hacky method. The concept involves encapsulating the underlying function within an object with a method for performing composition. Instead of naming the method compose, it could be named _ to minimize noise.

// Class and example implementation included for reference

While not as elegant as compose(f, g, h, k), this method offers a less cumbersome alternative that scales better than using numerous overloads.

With the introduction of Typescript 4, variadic tuple types offer a new way to construct a function whose signature is deduced from any number of input functions.

let compose = <T, V>(...args: readonly [
        (x: T) => any,          // 1. The first function type
        ...any[],               // 2. The middle function types
        (x: any) => V           // 3. The last function type
    ]): (x: V) => T =>          // The composed function signature type
{
    return (input: V) => args.reduceRight((val, fn) => fn(val), input);
};

let pipe = <T, V>(...args: readonly [
        (x: T) => any,          // 1. The first function type
        ...any[],               // 2. The middle function types
        (x: any) => V           // 3. The last function type
    ]): (x: T) => V =>          // The piped function signature type
{
    return (input: T) => args.reduce((val, fn) => fn(val), input);
};

However, there are still two limitations associated with this approach:

1. The compiler cannot validate that the output of each function matches the input of the next one
2. The compiler may raise an error when utilizing the spread operator (although it can infer the composed signature successfully)

For example, the following code will compile and execute correctly at runtime:

let f = (x: number) => x * x;
let g = (x: number) => `1${x}`;
let h = (x: string) => ({x: Number(x)});


let foo = pipe(f, g, h);
let bar = compose(h, g, f);

console.log(foo(2)); // => { x: 14 }
console.log(bar(2)); // => { x: 14 }

On the other hand, the following code will trigger a runtime error but still infer the correct signature and execute:

let fns = [f, g, h];
let foo2 = pipe(...fns);

console.log(foo2(2)); // => { x: 14 }

Check out this robust example of a strongly-typed compose function in TypeScript. While it may have the limitation of not verifying each individual function type along the way, it excels at determining the argument and return types for the final composed function.

Strongly-Typed Compose Function

/** Definition for single argument function */
type Function<Arg, Return> = (arg: Arg) => Return;

/**
 * Combines 1 to n functions.
 * @param func initial function
 * @param funcs additional functions
 */
export function compose<
  F1 extends Function<any, any>,
  FN extends Array<Function<any, any>>,
  R extends
    FN extends [] ? F1 :
    FN extends [Function<infer A, any>] ? (a: A) => ReturnType<F1> :
    FN extends [any, Function<infer A, any>] ? (a: A) => ReturnType<F1> :
    FN extends [any, any, Function<infer A, any>] ? (a: A) => ReturnType<F1> :
    FN extends [any, any, any, Function<infer A, any>] ? (a: A) => ReturnType<F1> :
    FN extends [any, any, any, any, Function<infer A, any>] ? (a: A) => ReturnType<F1> :
    Function<any, ReturnType<F1>> // Unlikely scenario to pipe so many functions, but we can still infer the return type if needed
>(func: F1, ...funcs: FN): R {
  const allFuncs = [func, ...funcs];
  return function combined(raw: any) {
    return allFuncs.reduceRight((memo, func) => func(memo), raw);
  } as R
}

Example Implementation:

// The compiler can recognize that the input type is Date from the last function
// and the return type is string from the first
const composition: Function<Date, string> = compose(
  (a: number) => String(a),
  (a: string) => a.length,
  (a: Date) => String(a)
);

const outcome: string = composition(new Date());

Technical Workings: We apply reduceRight on an array of functions to pass input through each function starting from the last one to the first. To determine the return type of compose, we infer the argument type based on the last function's argument type and the final return type based on the first function's return type.

Strongly-Typed Pipe Function

In addition to the compose function, we can create a strongly-typed pipe function to sequentially process data through each function.

/**
 * Establishes a sequence of functions.
 * @param func initial function
 * @param funcs additional functions
 */
export function pipe<
  F1 extends Function<any, any>,
  FN extends Array<Function<any, any>>,
  R extends
    FN extends [] ? F1 :
    F1 extends Function<infer A1, any> ?
      FN extends [any] ? Function<A1, ReturnType<FN[0]>> :
      FN extends [any, any] ? Function<A1, ReturnType<FN[1]>> :
      FN extends [any, any, any] ? Function<A1, ReturnType<FN[2]>> :
      FN extends [any, any, any, any] ? Function<A1, ReturnType<FN[3]>> :
      FN extends [any, any, any, any, any] ? Function<A1, ReturnType<FN[4]>> :
      Function<A1, any> // Unlikely scenario to pipe so many functions, but we can infer the argument type even when the return type is uncertain
    : never
>(func: F1, ...funcs: FN): R {
  const allFuncs = [func, ...funcs];
  return function processed(raw: any) {
    return allFuncs.reduce((memo, func) => func(memo), raw);
  } as R
}

Usage Example:

// The compiler infers the argument type as number based on the first function's argument type and 
// deduces the return type from the last function's return type
const piping: Function<number, string> = pipe(
  (a: number) => String(a),
  (a: string) => Number('1' + a),
  (a: number) => String(a)
);

const output: string = piping(4); // results in '14'

Utilizing the enhanced tuple types in TypeScript 4, it is possible to type functions like pipe and compose without the need for specifying overrides.

The compiler guarantees that each function can be called with the next one as expected, ensuring type checking for each intermediate function.

Explore the examples below in the instantiation expressions as of TypeScript 4.7.

function add3(x: number): number {
  return x + 3;
}

function stringify(x: number): string {
  return x.toString();
}

function identity<T>(t: T): T {
  return t;
}

const composed = compose(
  stringify,
  // Need instantiations from TS 4.7 for generics
  identity<string>,
  add3
);
console.log(composed(0));

I have discovered that crafting a typed compose function is quite manageable now (specifically for TypeScript v4.1.5 and newer, extensively tested in the type Compose<F> = (F extends [infer F1, infer F2, ...infer RS] ? (RS extends [] ? (F1 extends (...args: infer P1) => infer R1 ? (F2 extends (...args: infer P2) => infer R2 ? ([R1] extends P2 ? (...args: P1) => R2 : never) : never) : never) : Compose<[Compose<[F1, F2]>, ...RS]>) : never); type ComposeArgs<T> = Parameters<Compose<T>>; type ComposeReturn<T> = ReturnType<Compose<T>>; // I forget that composition is from right to left! type Reverse<T extends unknown[], RE extends unknown[] = []> = T extends [infer F, ...infer RS] ? Reverse<RS, [F, ...RE]> : RE; function composeL2R<T extends Function[]>(...fns: T): (...args: ComposeArgs<T>) => ComposeReturn<T> { return (...args: ComposeArgs<T>): ComposeReturn<T> => fns.reduce((acc: unknown, cur: Function) => cur(acc), args); } function compose<T extends Function[]>(...fns: T): (...args: ComposeArgs<Reverse<T>>) => ComposeReturn<Reverse<T>> { return (...args: ComposeArgs<Reverse<T>>): ComposeReturn<Reverse<T>> => fns.reduceRight((acc: unknown, cur: Function) => cur(acc), args); } function fns(x: number): string { return `${x}0`; } function fnn(x: number): number { return 2 * x; } function fsn(x: string): number { return parseInt(x); } let aNumber = compose(fsn, fns, fnn, fsn, fns, () => 1)(); let aNumberL2R = composeL2R(() => 1, fns, fsn, fnn, fns, fsn)(); let aNever = composeL2R(fnn, fsn, fns)(1); let aNeverL2R = composeL2R(fnn, fsn, fns)(1);

After thorough investigation, I stumbled upon an ingenious recursive approach shared by '@cartersnook6139' in the comments of Matt Pocock's video discussing a typed compose function. For those interested, here is the link to explore the Typescript Playground. It's pure magic!

declare const INVALID_COMPOSABLE_CHAIN: unique symbol;

type Comp = (arg: any) => any;

type IsValidChain<T extends ((arg: never) => any)[]> =
    T extends [infer $First extends Comp, infer $Second extends Comp, ...infer $Rest extends Comp[]]
        ? [ReturnType<$First>] extends [Parameters<$Second>[0]]
            ? IsValidChain<[$Second, ...$Rest]>
        : (T extends [any, ...infer $Rest] ? $Rest["length"] : never)
    : true;

type ReplaceFromBack<T extends unknown[], Offset extends number, Item, $Draft extends unknown[] = []> =
    $Draft["length"] extends Offset
        ? $Draft extends [any, ...infer $After]
            ? [...T, Item, ...$After]
        : never
    : T extends [...infer $Before, infer $Item]
        ? ReplaceFromBack<$Before, Offset, Item, [$Item, ...$Draft]>
    : never;

type asdf = ReplaceFromBack<[1, 2, 3, 4, 5, 6, 7, 8, 9], 3, "hey">;

function compose<Composables extends [Comp, ...Comp[]]>(
  ...composables:
        IsValidChain<Composables> extends (infer $Offset extends number)
            ? ReplaceFromBack<Composables, $Offset, "INVALID_COMPOSABLE">
        : Composables
) {
  return (
    firstData: Parameters<Composables[0]>[0]
  ): Composables extends [...any[], infer $Last extends (arg: never) => any]
    ? ReturnType<$Last>
    : never => {
    let data: any = firstData;
    for (const composable of composables) {
      data = (composable as any)(data);
    }
    return data;
  };
}

const addOne = (a: number): number => a + 1;
const numToString = (a: number): string => a.toString();
const stringToNum = (a: string): number => parseFloat(a);

namespace CorrectlyPassing {
  const v0 = compose(addOne, numToString, stringToNum); 
  //    ^?

  const v1 = compose(addOne, addOne, addOne, addOne, addOne, numToString);
  //    ^?

  const v2 = compose(numToString, stringToNum, addOne);
  //    ^?

  const v3 = compose(addOne, addOne, addOne);
  //    ^?
}

namespace CorrectlyFailing {
  // :o they actually show the error next to the incorrect one!
  compose(addOne, stringToNum);
  compose(numToString, addOne);
  compose(stringToNum, stringToNum);
  compose(addOne, addOne, addOne, addOne, stringToNum);
  compose(addOne, addOne, addOne, addOne, stringToNum, addOne);
}