typescript - 按一层或多层嵌套分组

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在T ， objects 的元素类型数组，以及 K ，一个tuple T 的按键对应...by rest parameter 。该函数返回 GroupedBy<T, K> .

那什么是GroupedBy<T, K> ？这是recursive conditional type 。如果元组 K为空，那么它就只是T[] (因为不按任何值对数组进行分组应该会产生相同的数组)。否则，我们使用 variadic tuple types拆分K元组到第一个元素 K0 ，其余的，KR 。然后GroupedBy<T, K>将是 Map其键类型是 T 的属性类型关键K0 (从概念上讲，这只是一个 indexed access type T[K0] ，但编译器不知道 K0 将是 T 的键，所以我们使用 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 )，因此让我们通过将其设为 overloaded function 来放松一下。具有单个强类型调用签名和使用 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数组为空，返回objects数组不变；这对应于 GroupedBy<T, K> 的基本情况哪里K是 [] 。否则，我们 split by进入第一个元素k0其余的 kr 。然后，我们对 objects 进行顶级分组。通过k0中的值 key 。这涉及到确保我们在将内容插入数组之前初始化数组是正确的。最后，最后，我们转换顶级分组(使用 this technique )，递归，应用 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