Typescript Cartesian Product

cartesianProduct.ts

const f = (a: any[], b: any[]): any[] =>
    [].concat(...a.map(a2 => b.map(b2 => [].concat(a2, b2))));

export const cartesianProduct = (a: any[], b: any[], ...c: any[]) => {    
    if (!b || b.length === 0) {
        return a;
    }
    const [b2, ...c2] = c;
    const fab = f(a, b);
    return cartesianProduct(fab, b2, c2);
};

@SgtPooki Thanks for the link, that's also a nice read! The author is optimizing at a much lower level. The issue I was referring to (quadratic complexity due to the usage of the spread operator in loops) comes even before that. You don't need to understand much JavaScript to avoid quadratic complexity if possible :)

@albertodiazdorado It is not "awful", it is working as expected, as T can infer any type of value here.

Example with 3 different types:

If you want to enforce the type of each dimension of your array, you should consider functions overloading like this:

@cr0cK

export function cartesianProduct<T>(...allEntries: T[][]): T[][] {
    return allEntries.reduce<T[][]>(
      (results, entries) =>
        results
          .map(result => entries.map(entry => result.concat([entry])))
          .reduce((subResults, result) => subResults.concat(result), []),
      [[]]
    )
  }


const numbers = [1,2,3,4];
const strings = ["1", "2", "3", "4"];

// Argument of type 'string[]' is not assignable to parameter of type 'number[]'.
//  Type 'string' is not assignable to type 'number'.ts(2345)
const product = cartesianProduct(numbers, strings);

First of all, the inference is not working properly. But even if we aid the compiler, the types are still awful:

export function cartesianProduct<T>(...allEntries: T[][]): T[][] {
    return allEntries.reduce<T[][]>(
      (results, entries) =>
        results
          .map(result => entries.map(entry => result.concat([entry])))
          .reduce((subResults, result) => subResults.concat(result), []),
      [[]]
    )
  }


const numbers = [1,2,3,4];
const strings = ["1", "2", "3", "4"];

const product = cartesianProduct<number | string>(numbers, strings);

// Property 'length' does not exist on type 'string | number'.
//  Property 'length' does not exist on type 'number'.ts(2339)
console.log(product[0][1].length)

We know with certainty that the second element of the cartesian product is a string. However, your implementation loses that information. That's not what I expect from a type system. I want a type system to help me, not make my work harder.

That is how you "expect" it to work?

Indeed, the inference does not work with your example.

But my simple recommendation here:

Try to avoid mixing types when you can. Here for a cartesian product, I'm not sure it makes a lot of sense to mix strings and numbers.

I want a type system to help me, not make my work harder.

A type system is also here to help you to design things the right way. If the implementation becomes too complex, it generally means that something is wrong. You do not implement things the same way when using typings. If you're not happy with that, you should go back to JS.

Tell me that you cannot solve the problem of the cartesian product in TypeScript without telling me that you cannot solve the problem of the cartesian product in TypeScript.

Which is fine, by the way. I don't know the solution either. I came here looking for the solution and make the note that the proposed solution is wrong, in the sense explained in the comment above. Nothing else.

If you find the right solution, I'd be glad if you posted it here.

Mixed types are tricky.
Give this a try.

The key is [...T]

export const cartesianProduct = <T extends any[][]>(a: [...T]): Array<{[K in keyof T]: T[K][number]}> => a.reduce((a, b) => a.flatMap(d => b.map(e => [d, e].flat())))