Can recursively variadic functions be typed in Typescript?

Question

I have the following generic function I can derive various useful variadic functions from:

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

  return go([]);
};

const arrFold = alg => zero => xs =>
  xs.reduce((acc, x) => alg(acc) (x), zero);

const comp = f => g => x => f(g(x));
const id = x => x;

const varComp = variadic(arrFold(comp) (id));

const inc = x => x + 1;

const main = varComp(inc) (inc) (inc) (inc) (inc);

console.log(
  main.runVariadic(0)); // 5

This sort of recursively variadic interface allows me to maintain a flat application syntax without relying on method chaining. Additionally I can partially apply and compose such functions. Unfortunately variadic and the derived varComp have infinite types. I vaguely recall that in Haskell there is a way to type such functions anyway but it requires a lot of type machinery, namley advanced language extensions. Is there a trick to type them in Typescript?

I am a Typescript newbie so I don't even know where to start.

Answer 1

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