如何利用 TypeScript 可变元组类型实现笛卡尔积函数？

Question

如何利用 TypeScript 可变元组类型实现笛卡尔积函数？

typescriptcartesian-producttypescript4.0variadic-tuple-types

3

TypeScript 4.0开始支持可变元组类型的概念，这是一种很好的类型构造，可以在连接函数中使用。以下是来自文档的一个示例：

type Arr = readonly any[];

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

我对于这种类型构造能否用于为笛卡尔积函数进行类型标注很感兴趣。该函数应该能够根据其参数推断出（混合的）类型，并生成相应的返回类型。因此，如果我输入[number[], string[]]，则期望输出的类型为[number, string][]。在这个线程中可以找到多个笛卡尔积的实现，但没有一个是严格类型化的。以下是一个例子：

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

我目前使用的实现不利用变长元组类型，需要显式类型转换：

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']);

我正在寻找一种不需要显式类型转换的解决方案，我认为可变元组类型可能是适当的类型构造。

问题如何使用可变元组类型推断笛卡尔积函数的类型？

- Nicky

3个回答

1

如果是笛卡尔积，我们应该使用集合而不是数组。无论是输入还是输出都是如此。

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']));

编辑（在Nicky的评论后）：

我试图将函数签名推广到任意数量的集合，但无法从数组切换到集合。

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]);

但是后来我仔细阅读了@Titian Cernicova-Dragomir的答案，他使用了很好的类型推断，所以我采用了他的方法来处理集合。

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]));

- Tomasz Gawel

谢谢你的回答，但不幸的是，那并不是问题所涉及的内容。 - undefined

@Nicky 好的，顺便问一下，你需要这个用于两个“集合”的笛卡尔积吗？还是更多？ - undefined

我需要无限数量的集合，因此它应该处理N个不同的输入（而不是两个）。 - undefined

抱歉，我误解了原问题。但是@Titian Cernicova-Dragomir提供的解决方案似乎完全没问题，对吧？ - undefined

0

正如Titian所说，变长元组类型在这里并不是真正必要的。你还可以通过将泛型T表示为每个输入数组的内部类型来实现更紧凑的解决方案，比Titian的解决方案更紧凑。此外，你应该使用unknown作为any的更安全的替代方案。

const cartesian = <T extends unknown[]>(...a: { [K in keyof T]: T[K][] }) =>
    a.reduce<T[]>(
        (b, c) => b.flatMap((d) => c.map((e) => [...d, e] as T)),
        [[]] as unknown as T[]
    );

- cabralpinto

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Titian Cernicova-Dragomir · Accepted Answer

我认为变长元组类型并没有实际改善我们输入的方式。自从3.1版本引入元组映射支持后，输入这个已经是可能的了（可能在此之前也是可以实现的，但不如现在干净）。

在实际实现中仍需要类型断言，但调用端会推断参数类型，并产生正确的返回类型：

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链接