Skip to content

Instantly share code, notes, and snippets.

@ssippe
Created April 20, 2017 00:33
Show Gist options
  • Save ssippe/1f92625532eef28be6974f898efb23ef to your computer and use it in GitHub Desktop.
Save ssippe/1f92625532eef28be6974f898efb23ef to your computer and use it in GitHub Desktop.
Typescript Cartesian Product
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);
};
@albertodiazdorado
Copy link

@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 :)

@cr0cK
Copy link

cr0cK commented Oct 27, 2023

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

Example with 3 different types:

Screenshot from 2023-10-27 15-37-07

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

image

@albertodiazdorado
Copy link

@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?

@cr0cK
Copy link

cr0cK commented Oct 27, 2023

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.

@albertodiazdorado
Copy link

albertodiazdorado commented Oct 29, 2023

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.

@please-rewrite
Copy link

please-rewrite commented Oct 31, 2023

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())))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment