How to utilise TypeScript Variadic Tuple Types for a Cartesian Product function?

user_3930694 0
Viewed 903

TypeScript 4.0 started to support the notion of Variadic Tuple Types, a nice type construct that can be used in e.g. concatenation functions. An example from the docs:

type Arr = readonly any[];

function concat<T extends Arr, U extends Arr>(arr1: T, arr2: U): [...T, ...U] {
  return [...arr1, ...arr2];
}

I am interested in whether this type construct can be used to type a Cartesian Product function. The function should then infer the (mixed) types from the arguments to produce its return type. So if I input [number[], string[]] I would expect the output to be of type [number, string][]. Multiple implementations for a Cartesian Product can be found in this thread, but none is strictly typed. Here is an example:

const cartesian =
  (...a) => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())));

An implementation I currently use does not utilise Variadic Tuple Types and needs explicit type casting:

const cartesian = <T extends any[]>(...arr: any[][]): T[] =>
  arr.reduce<T[]>(
    (a, b) => a.flatMap<T>(c => b.map<T>(d => [...c, d] as T)),
    [[]] as T
  );

const product = cartesian<[number, string]>([1, 2, 3], ['a', 'b', 'c']);

I am looking for a solution without explicit type casting and I think Variadic Tuple Types may be the appropriate type construct here.

Question

How can I use Variadic Tuple Types to infer the types of a Cartesian Product function?

variadic-tuple-types typescript4.0 typescript cartesian-product
2 Answers

I don't think Variadic Tuple Types actually improves the way we can type this. Typing this has actually been possible since support for mapping tuples was added in 3.1 (was probably possible before but not as cleanly).

You will still need a type assertion in the actual implementation, but the call site will infer the argument types and produce the correct return type:

type MapCartesian<T extends any[][]> = {
  [P in keyof T]: T[P] extends Array<infer U>? U: never
}
const cartesian = <T extends any[][]>(...arr: T): MapCartesian<T>[] =>
  arr.reduce(
    (a, b) => a.flatMap(c => b.map(d => [...c, d] )),
    [[]] 
  ) as MapCartesian<T>[];

const product = cartesian([1, 2, 3], ['a', 'b', 'c']);

Playground Link

user_1257340

If it's cartesian product we should rather use Set instead of arrays. Both for input as for output.

function cartesian<X, Y>(setX: Set<X>, setY: Set<Y>): Set<[X, Y]> {
    const result = new Set<[X, Y]>();
    setX.forEach(x => setY.forEach(y => result.add([x, y])));
    return result;
}

const product = cartesian(new Set([1, 2, 3]), new Set(['a', 'b', 'c']));

EDIT (after Nicky's comment):

I tried to generalize the function signature for any number of sets but, could not switch from array to set:

declare function cartesian<A extends Array<Array<any>>>(
    ...args: A): { [K in keyof A]: A[K] extends Array<any> ? A[K][number] : never }[];
const product = cartesian([1, 2, 3], ['a', 'b', 'c'], [true, false]);

but then I read carefully the answer by @Titian Cernicova-Dragomir, with nice type inference so I used his approach for sets:

declare function cartesian<A extends Array<Set<any>>>(
    ...args: A): Set<{ [K in keyof A]: A[K] extends Set<infer T> ? T : never }>;
const product = cartesian(new Set([1, 2, 3]), new Set(['a', 'b', 'c']), 
    new Set([true, false]));
user_10108680
Related