Generic curry function with TypeScript 3

Question

TypeScript 3.0 introduced generic rest parameters.

Up until this point, curry functions had to be annotated in TypeScript with a finite number of function overloads and a series of conditional statements querying the number of passed arguments within the implementation.

I am hoping that generic rest parameters finally offer the mechanism needed to implement a completely generic solution.

I would like to know how to use this new language feature to write a generic curry function... assuming it's possible of course!

The JS implementation using rest params that I modified a little from a solution I found on hackernoon looks like this:

function curry(fn) {
  return (...args) => {
    if (args.length === 0) {
      throw new Error("Empty invocation")
    } else if (args.length < fn.length) {
      return curry(fn.bind(null, ...args))
    } else {
      return fn(...args)
    }
  }
}

Using generic rest params and function overloads, my attempt at annotating this curry function in TypeScript looks like this:

interface CurriedFunction<T extends any[], R> {
  (...args: T): void // Function that throws error when zero args are passed
  (...args: T): CurriedFunction<T, R> // Partially applied function
  (...args: T): R // Fully applied function
}

function curry<T extends any[], R>(
  fn: CurriedFunction<T, R>
): CurriedFunction<T, R> {
  return (...args: T) => {
    if (args.length === 0) {
      throw new Error("Empty invocation")
    } else if (args.length < fn.length) {
      return curry(fn.bind(null, ...args))
    } else {
      return fn(...args)
    }
  }
}

However TypeScript throws the error:

Type 'CurriedFunction<any[], {}>' is not assignable to type 'CurriedFunction<T, R>'.
Type '{}' is not assignable to type 'R'.

I don't understand where and why R is being inferred as {}?

Answer 1

Right now the biggest hurdle for typing this correctly is TypeScript's inability to concatenate or split tuples as of TypeScript 3.0. There are suggestions for doing this, and something might be in the works for TypeScript 3.1 and beyond, but it's just not there right now. As of today all you could do is enumerate cases up to some maximum finite length, or try to trick the compiler into using recursion which is not recommended.

If we imagine that there were a TupleSplit<T extends any[], L extends number> type function which could take a tuple and a length and split the tuple at that length into the initial component and the rest, so that TupleSplit<[string, number, boolean], 2> would produce {init: [string, number], rest: [boolean]}, then you could declare your curry function's type as something like this:

declare function curry<A extends any[], R>(
  f: (...args: A) => R
): <L extends TupleSplit<A, number>['init']>(
    ...args: L
  ) => 0 extends L['length'] ?
    never :
    ((...args: TupleSplit<A, L['length']>['rest']) => R) extends infer F ?
    F extends () => any ? R : F : never;

For the sake of being able to try that, let's introduce a version of TupleSplit<T, L> that only works for L up to 3 (which you can add to if you want). It looks like this:

type TupleSplit<T extends any[], L extends number, F = (...a: T) => void> = [
  { init: [], rest: T },
  F extends ((a: infer A, ...z: infer Z) => void) ?
  { init: [A], rest: Z } : never,
  F extends ((a: infer A, b: infer B, ...z: infer Z) => void) ?
  { init: [A, B], rest: Z } : never,
  F extends ((a: infer A, b: infer B, c: infer C, ...z: infer Z) => void) ?
  { init: [A, B, C], rest: Z } : never,
  // etc etc for tuples of length 4 and greater
  ...{ init: T, rest: [] }[]
][L];

Now we can test that declaration of curry on a function like

function add(x: number, y: number) {
  return x + y;
}
const curriedAdd = curry(add);

const addTwo = curriedAdd(2); // (y: number) => number;
const four = curriedAdd(2,2); // number
const willBeAnError = curriedAdd(); // never

Those types look correct to me.

---

Of course, that doesn't mean the implementation of curry will be happy with that type. You might be able to implement it like:

return <L extends TupleSplit<A, number>['init']>(...args: TupleSplit<A, L['length']>['rest']) => {
  if (args.length === 0) {
    throw new Error("Empty invocation")
  } else if (args.length < f.length) {
    return curry(f.bind(null, ...args))
  } else {
    return f(...args as A)
  }
}

possibly. I haven't tested that.

Anyway, hope that makes some sense and gives you some direction. Good luck!

---

UPDATE

I didn't pay attention to the fact that curry() returns further curried functions, if you don't pass in all the arguments. Doing that requires a recursive type, like this:

type Curried<A extends any[], R> =
  <L extends TupleSplit<A, number>['init']>(...args: L) =>
    0 extends L['length'] ? never :
    0 extends TupleSplit<A, L['length']>['rest']['length'] ? R :
    Curried<TupleSplit<A,L['length']>['rest'], R>;

declare function curry<A extends any[], R>(f: (...args: A)=>R): Curried<A, R>;

function add(x: number, y: number) {
  return x + y;
}
const curriedAdd = curry(add);

const addTwo = curriedAdd(2); // Curried<[number], number>
const three = addTwo(1); // number
const four = curriedAdd(2,2); // number
const willBeAnError = curriedAdd(); // never

That's more like the original definition.

---

But I also notice that if you do this:

const wat = curriedAdd("no error?"); // never

that instead of getting an error, it returns never. This looks like a compiler bug to me, but I haven't followed it up yet. EDIT: Okay, I filed Microsoft/TypeScript#26491 about this.

Cheers!

Answer 2

With the current version of typescript, it is possible to create a relatively simple correctly typed generic curry function.

type CurryFirst<T> = T extends (x: infer U, ...rest: any) => any ? U : never;
type CurryRest<T> =
    T extends (x: infer U) => infer V ? U :
    T extends (x: infer U, ...rest: infer V) => infer W ? Curried<(...args: V) => W> :
    never

type Curried<T extends (...args: any) => any> = (x: CurryFirst<T>) => CurryRest<T>

const curry = <T extends (...args: any) => any>(fn: T): Curried<T> => {
    if (!fn.length) { return fn(); }
    return (arg: CurryFirst<T>): CurryRest<T> => {
        return curry(fn.bind(null, arg) as any) as any;
    };
}

describe("Curry", () => {
    it("Works", () => {
        const add = (x: number, y: number, z: number) => x + y + z;
        const result = curry(add)(1)(2)(3)
        result.should.equal(6);
    });
});

This is based on two type constructors:

• CurryFirst will given a function return the type of the first argument for that function.
• CurryRest will return the return type of the curried function with the first argument applied. The special case is when the function type T only takes one argument, then CurryRest<T> will just return the return type of the function type T

Based on these two, the type signature for the curried version of function of type T simply becomes:

Curried<T> = (arg: CurryFirst<T>) => CurryRest<T>

I made some simple constraints here:

• You don't want to curry a parameterless function. You could easily add it, but I don't think it makes sense.
• I don't preserve the this pointer. This doesn't make sense to me either because we're entering pure FP land here.

Speculative performance improvements could be made if the curry function accumulates the parameters in an array, and performs one fn.apply, instead of multiple fn.bind calls. But care must be taken to make sure that partially applied functions can be correctly called multiple times.

Answer 3

The biggest problem here is that you're trying to define a generic function with a variable number of 'curried levels' -- e.g. a => b => c => d or x => y => z or (k, l) => (m, n) => o, where all of these functions are somehow represented by the same (albeit generic) type definition F<T, R> -- something that isn't possible in TypeScript as you can't arbitrarily split generic rests into two smaller tuples...

Conceptually you need:

FN<A extends any[], R> = (...a: A) => R | (...p: A.Prefix) => FN<A.Suffix, R>

TypeScript AFAIK cannot do this.

Your best bet would be to use some lovely overloads:

FN1<A, R>             = (a: A) => R
FN2<A, B, R>          = ((a: A, b: B) => R)             | ((a: A) => FN1<B, R>)
FN3<A, B, C, R>       = ((a: A, b: B, c: C) => R)       | ((a: A, b: B) => FN1<C, R>)       | ((a: A) => FN2<B, C, R>)
FN4<A, B, C, D, R>    = ((a: A, b: B, c: C, d: D) => R) | ((a: A, b: B, c: C) => FN1<D, R>) | ((a: A, b: B) => FN2<C, D, R>) | ((a: A) => FN3<B, C, D, R>)

function curry<A, R>(fn: (A) => R): FN1<A, R>
function curry<A, B, R>(fn: (A, B) => R): FN2<A, B, R>
function curry<A, B, C, R>(fn: (A, B, C) => R): FN3<A, B, C, R>
function curry<A, B, C, D, R>(fn: (A, B, C, D) => R): FN4<A, B, C, D, R>

Lots of languages have unrolled types like these baked-in, because few type systems support this level of recursive flow control when defining types.