JavaScript/TypeScript で配列の groupBy

## はじめに

groupBy を書いてみたメモ。

こういうのが揃っているライブラリもあるけれど、
バニラで書きたいときもあるし、
色々と応用も効きそうだしということで書き留め。

## 例

何かゲームの個人記録があったとして、
各チームの平均点が知りたい、みたいなケース。

~~~js
const records = [
    { player: 'a', team: 'red', score: 10 },
    { player: 'b', team: 'blue', score: 3 },
    { player: 'c', team: 'red', score: 4 },
    { player: 'd', team: 'green', score: 15 },
    // ...
];

/*
const result = [
    { team: 'red', score: ... },
    { team: 'blue', score: ... },
    { team: 'green', score: ... },
    // ...
]
*/
~~~

## ナイーブな実装

`filter` で振り分けちゃおうか、という発想。

~~~js
const result = ['red', 'blue', 'green']
    .map(team => {
        const list = records.filter(r => r.team === team);
        return {
            team,
            score: list.reduce((sum, r) => sum + r.score, 0) / list.length
        };
    });
~~~

書くのは楽だけれど、`filter` のループ回数が要素数×分割数 になるので、
件数多いときにちょっと使いたくない感じ。

チームも決め打ちになってしまっているので、拡張性に乏しい。

やはり汎用的な groupBy が欲しい。

## groupBy オブジェクト版

グループに分け、結果を `{ key: values }` なオブジェクトで返す。

わりとよく見る実装。(underscore.js とか)

~~~js:js
const groupBy = (array, getKey) =>
    array.reduce((obj, cur, idx, src) => {
        const key = getKey(cur, idx, src);
        (obj[key] || (obj[key] = [])).push(cur);
        return obj;
    }, {});
~~~

~~~ts:ts
const groupBy = <K extends PropertyKey, V>(
    array: readonly V[],
    getKey: (cur: V, idx: number, src: readonly V[]) => K
) =>
    array.reduce((obj, cur, idx, src) => {
        const key = getKey(cur, idx, src);
        (obj[key] || (obj[key] = []))!.push(cur);
        return obj;
    }, {} as Partial<Record<K, V[]>>);
~~~

振り分けのループ回数が要素数に抑えられている。

~~~js:Usage
const groups = groupBy(records, r => r.team);
const result = Object.entries(groups)
    .map(([team, list]) => ({
        team,
        score: list.reduce((sum, r) => sum + r.score, 0) / list.length
    }));
~~~

単に振り分けるだけならいいのだけれど、その後になにか続けようとすると、ちょっと使い勝手が悪い。

他にも色々と不満点がある。

- 振り分けがオブジェクトのキーに出来るもの (`string`, `number`, `symbol`) に限定される。
- ケースによっては、グループの順序が登場した順にならない。
    - (参考: [ES6 以降は JavaScript のプロパティに順序は「ある」 - Qiita](https://qiita.com/nagtkk/items/6fb99ef4c51883e9b965))

## groupBy タプル版

オブジェクト `{ key: values }` ではなくタプル群 `[key, values][]` を返すようにしよう。

~~~js:js
const groupBy = (array, getKey) =>
    Array.from(
        array.reduce((map, cur, idx, src) => {
            const key = getKey(cur, idx, src);
            const list = map.get(key);
            if (list) list.push(cur);
            else map.set(key, [cur]);
            return map;
        }, new Map())
    );
~~~

~~~ts:ts
const groupBy = <K, V>(
    array: readonly V[],
    getKey: (cur: V, idx: number, src: readonly V[]) => K
): [K, V[]][] =>
    Array.from(
        array.reduce((map, cur, idx, src) => {
            const key = getKey(cur, idx, src);
            const list = map.get(key);
            if (list) list.push(cur);
            else map.set(key, [cur]);
            return map;
        }, new Map<K, V[]>())
    );
~~~

使い方。

~~~js:Usage
const result = groupBy(items, item => item.team)
    .map(([team, items]) => ({
        team: team,
        score: items.reduce((sum, item) =>
            sum + item.score, 0) / items.length
    }));
~~~

そうそう、せめてこうでなくては。

返してくるのが配列なので素直に続けて書ける。

振り分けに `Map` を使用しているので、グループ登場順が維持される。
また、`boolean` や `object` (参照) も振り分けに使える。

最終的にオブジェクトにしたい場合も、ES2019 以降であれば `Object.fromEntries` を用いて変換できる。

~~~js
const objGroupBy = (array, getKey) =>
    Object.fromEntries(groupBy(array, getKey));
~~~

~~~ts
const objGroupBy = <K extends PropertyKey, V>(
    array: readonly V[],
    getKey: (cur: V, idx: number, src: readonly V[]) => K
) =>
    Object.fromEntries(groupBy(array, getKey)) as
    Partial<Record<K, V[]>>;
~~~

## 応用: インデックス分配 (配列→配列の配列)

ちょっと方向を変えて、キーで分類するのではなくて、
インデックスで分類し、配列の配列を返すものも作ってみる。

groupBy の亜種みたいなものだけれど、これが何かと便利。

~~~js:javascript
const scatter = (array, getIndex) =>
    array.reduce((result, cur, idx, src) => {
        const i = getIndex(cur, idx, src) | 0;
        if (i >= 0) (result[i] || (result[i] = [])).push(cur);
        return result;
    }, []);
~~~

~~~ts:typescript
const scatter = <T>(
    array: readonly T[],
    getIndex: (cur: T, idx: number, src: readonly T[]) => number
) =>
    array.reduce((result, cur, idx, src) => {
        const i = getIndex(cur, idx, src) | 0;
        if (i >= 0) (result[i] || (result[i] = [])).push(cur);
        return result;
    }, [] as T[][]);
~~~

こんな感じ。

~~~js:Usage
const a = [1, 2, 3, 4];
const [even, odd] = scatter(a, x => x % 2);

console.log(even); // [2, 4]
console.log(odd);  // [1, 3]
~~~

### 振り分け (groupBy 代わり)

~~~js
// 各商品は、0 以上 10 未満の人気度(レーティング)を持っている。
const items = [
    { name: 'minor', rating: 3.8, desc: "..." },
    { name: 'niche', rating: 1.5, desc: "..." },
    { name: 'major', rating: 9.0, desc: "..." },
    // ...
];

// 3段階にランク分け
const [low = [], middle = [], high = []] =
    scatter(items, item => item.rating / 10 * 3 | 0);
~~~

### バケットソート

そのまま `flat` すれば、いわゆるバケットソートと同じことになる。

~~~js
// レーティング順でなくランク順、ランク内の順序は維持
const rankedItems = scatter(items,
    item => item.rating / 10 * 3 | 0).flat();
~~~

### サイズ分割

元のインデックスを用いれば、配列を分割できる。

~~~js
const chunk = (a, n) => scatter(a, (_, i) => i / n | 0);

chunk([0,1,2,3,4,5], 3); // [[0,1,2], [3,4,5]]
~~~

行列周りに応用してみたりとか。

~~~js
const array = [
    0, 1, 2, 3,
    4, 5, 6, 7,
    8, 9, 10, 11,
    12, 13, 14, 15
];

const rowMatrix = scatter(array, (_, i) => i / 4 | 0);
// [
//   [0, 1, 2, 3],
//   [4, 5, 6, 7],
//   [8, 9, 10, 11],
//   [12, 13, 14, 15]
// ]

const colMatrix = scatter(array, (_, i) => i % 4);
// [
//   [0, 4, 8, 12],
//   [1, 5, 9, 13],
//   [2, 6, 10, 14],
//   [3, 7, 11, 15]
// ]

// 行と列の入れ替え
const transpose = m => scatter(m.flat(), (_, i) => i % m[0].length);

const mat = [
  [0, 1, 2],
  [3, 4, 5]
];
console.log(transpose(mat));
// [
//   [0, 3],
//   [1, 4],
//   [2, 5]
// ]
console.log(transpose(transpose(mat))); // 元に戻る
~~~

### おまけ: 疎な配列を埋める・詰める

`scatter` で返ってくる配列は、疎な配列の可能性があるので、便利関数もついでに。

~~~js:js
const fillEmpty = (array, supply) => Array.from(array,
    (x, i) => array.hasOwnProperty(i) ? x : supply(i));

const skipEmpty = array => array.filter(() => true);
~~~

~~~ts:ts
const fillEmpty = <T>(array: readonly T[], supply: (i: number) => T) =>
    Array.from(array, (x, i) => array.hasOwnProperty(i) ? x : supply(i));

const skipEmpty = <T>(source: readonly T[]) =>
    source.filter(() => true);
~~~

~~~js:Usage
const sparse = [0, , 2, , 4, , 6];
// [0, <empty>, 2, <empty>, 4, <empty>, 6]

// 空き領域を値で埋める。
const filled = fillEmpty(sparse, _ => 0);
// [0, 0, 2, 0, 4, 0, 6]

// 空き領域を詰める
const packed = skipEmpty(sparse);
// [0, 2, 4, 6]
~~~