按一个或多个级别嵌套分组

Question

给定以下数据结构：

const data = [
  { A: 1, B: 12, C: 123 },
  { A: 1, B: 122, C: 1233 },
  { A: 2, B: 22, C: 223 }
];

我想使用以下签名实现名为 groupBy 的函数：

function groupBy<T, By extends keyof T>(object: T[], by: ...By[]): Map<By[0], Map<By[1], ..., Map<number, T[]>...>

我可以这样称呼：

const A = groupBy(data, "A"); // Map<number, { A: number, B: number, C: number }[]>;
const AB = groupBy(data, "A", "B"); // Map<number, Map<number, { A: number, B: number, C: number }[]>>;
const ABC = groupBy(data, "A", "B", "C"); // Map<number, Map<number, Map<number, ...>>;

不幸的是，我只能implement groupBy with a single level:

function groupBy<T extends object, K extends keyof T>(collection: T[], iteratee: K): Map<T[K], T[]> {
  const map: Map<T[K], T[]> = new Map();

  for (const item of collection) {
    const accumalated = map.get(item[iteratee]);
    if (accumalated === undefined) {
      map.set(item[iteratee], [item]);
    } else {
      map.set(item[iteratee], [...accumalated, item]);
    }
  }

  return map;
}

Answer 1

首先让我们在类型级别描述 groupBy()，给它一个强类型的调用签名：

type GroupedBy<T, K> = K extends [infer K0, ...infer KR] ?
    Map<T[Extract<K0, keyof T>], GroupedBy<T, KR>> : T[];

// call signature
function groupBy<T, K extends Array<keyof T>>(
  objects: readonly T[], ...by: [...K]
): GroupedBy<T, K>;

所以 groupBy() 是 generic in T, the type of the elements of the objects array, as well as K, a tuple of the keys of T corresponding to the ...by rest parameter。函数 returns GroupedBy<T, K>.

那么 GroupedBy<T, K> 是什么？这是一个 recursive conditional type. If the tuple K is empty, then it will just be T[] (since grouping an array by nothing should yield the same array). Otherwise, we use variadic tuple types to split the K tuple into the first element, K0, and the rest, KR. Then GroupedBy<T, K> will be a Map whose key type is the type of property of T at key K0 (conceptually this is just an indexed access type T[K0], but the compiler doesn't know that K0 will be a key of T, so we use the Extract<T, U> utility type 说服它...所以 T[Extract<K0, keyof T>]) 并且其值类型是递归的 GroupedBy<T, KR>.

让我们确保编译器做正确的事情：

const A = groupBy(data, "A"); 
// Map<number, { A: number, B: number, C: number }[]>;

const AB = groupBy(data, "A", "B"); 
// Map<number, Map<number, { A: number, B: number, C: number }[]>>;

const ABC = groupBy(data, "A", "B", "C"); /* Map<number, Map<number, Map<number, {
    A: number;
    B: number;
    C: number;
}[]>>> */

看起来不错。为了确定，让我们将 number 更改为其他内容：

const otherData = [
    { str: "a", num: 1, bool: true },
    { str: "a", num: 1, bool: false },
    { str: "a", num: 2, bool: true }
];
const grouped = groupBy(otherData, "str", "num", "bool")
/* const grouped: Map<string, Map<number, Map<boolean, {
    str: string;
    num: number;
    bool: boolean;
}[]>>> */

看起来也不错。

现在让我们实施 groupBy()。编译器不可能在实现中遵循递归条件类型（参见 microsoft/TypeScript#33912), so let's loosen things up by making it an overloaded function with a single, strongly-typed call signature, and a loose implementation signature using the any type。我们必须小心地正确执行它，因为编译器不会捕获类型错误。

无论如何，这是一个可能的实现：

// implementation
function groupBy(objects: readonly any[], ...by: Array<PropertyKey>) {
    if (!by.length) return objects;
    const [k0, ...kr] = by;
    const topLevelGroups = new Map<any, any[]>();
    for (const obj of objects) {
        let k = obj[k0];
        let arr = topLevelGroups.get(k);
        if (!arr) {
            arr = [];
            topLevelGroups.set(k, arr);
        }
        arr.push(obj);
    }
    return new Map(Array.from(topLevelGroups, ([k, v]) => ([k, groupBy(v, ...kr)])));

}

如果by数组为空，returnobjects数组不变；这对应于 GroupedBy<T, K> 的基本情况，其中 K 是 []。否则，我们将 by 拆分为第一个元素 k0 和其余元素 kr。然后，我们通过 k0 键中的值对 objects 进行顶级分组。这涉及确保我们在将内容推入数组之前初始化数组。最后，在最后，我们转换顶级分组（使用），递归，将 groupBy() 应用于每个对象数组。

让我们看看它是否有效：

console.log(A);
/* Map (2) {1 => [{
  "A": 1,
  "B": 12,
  "C": 123
}, {
  "A": 1,
  "B": 122,
  "C": 1233
}], 2 => [{
  "A": 2,
  "B": 22,
  "C": 223
}]}  */

console.log(AB);
/* Map (2) {1 => Map (2) {12 => [{
  "A": 1,
  "B": 12,
  "C": 123
}], 122 => [{
  "A": 1,
  "B": 122,
  "C": 1233
}]}, 2 => Map (1) {22 => [{
  "A": 2,
  "B": 22,
  "C": 223
}]}}  */

看起来也不错。

Playground link to code

按一个或多个级别嵌套分组

Nested grouping by one or more levels

data-structures

typescript