TypeScriptでオブジェクトのリストを内部結合してみる

# はじめに

今回はTypeScriptでオブジェクトのリストをRDBのようにHash Joinしてみようという話題です。
あまり実用性はないかもしれませんが、TypeScriptで型を意識してコーディングするための練習としてやってみます。

:::note info
※ 私が株式会社愛宕 Advent Calendar 2023に書く記事は主に社内向けに共有しておきたいけど勉強会をするまでもないちょっとしたTipsにしたいと思います。
:::

次のようなオブジェクトのリストがあるとします。
本 `Book` と著者 `Author` のリストです。タイトルや著者名は今をときめく生成AIに**ユーモアを交えて**と指定して考えてもらいました。

```TypeScript
interface Book {
  id: string
  title: string
  publishDate: Date
}

interface Author {
  authorId: string
  authorName: string
  bookId: string
}

const books: Book[] = [
  { id: "B0001", title: "2100年のネットワークお悩み相談室", publishDate: "20990301" },
  { id: "B0002", title: "プログラミングの基本を1分でマスターする！", publishDate: "20240101" },
  { id: "B0003", title: "パソコンの電源を入れずにネットの誹謗中傷を消す方法", publishDate: "20380119" },
  { id: "B0004", title: "ロボットたちの休日: AIが作る非常識なバケーションガイド", publishDate: "20240931" },
  { id: "B0005", title: "エイリアンとデバッグ: 異星人から学ぶプログラミングの極意せ", publishDate: "20250301" },
]

const authors: Author[] = [
  { authorId: "A0001", authorName: "xxx", bookId: "B0001" },
  { authorId: "A0002", authorName: "1分師匠", bookId: "B0002" },
  { authorId: "A0003", authorName: "ジョン・イレイザー", bookId: "B0003" },
  { authorId: "A0004", authorName: "AI芸人ボット", bookId: "B0004" },
  { authorId: "A0005", authorName: "AI使い", bookId: "B0004" },
  { authorId: "A0006", authorName: "江戸川困難", bookId: "B0005" },
]
```

上記のような構造のリストをJoinして次のような出力を得たいとします。

```TypeScript
const booksWithAuthors = [
  { 
    id: "B0001", title: "2100年のネットワークお悩み相談室", publishDate: "20990301", 
    authorId: "A0001", authorName: "xxx" 
  },
  { 
    id: "B0002", title: "プログラミングの基本を1分でマスターする！", publishDate: "20240101", 
    authorId: "A0002", authorName: "1分師匠" 
  },
  { 
    id: "B0003", title: "パソコンの電源を入れずにネットの誹謗中傷を消す方法", publishDate: "20380119", 
    authorId: "A0003", authorName: "ジョン・イレイザー" 
  },
  { 
    id: "B0004", title: "ロボットたちの休日: AIが作る非常識なバケーションガイド", publishDate: "20240931", 
    authorId: "A0004", authorName: "AI芸人ボット" 
  },
  { 
    id: "B0004", title: "ロボットたちの休日: AIが作る非常識なバケーションガイド", publishDate: "20240931", 
    authorId: "A0005", authorName: "AI使い" 
  },
  { 
    id: "B0005", title: "エイリアンとデバッグ: 異星人から学ぶプログラミングの極意", publishDate: "20250301", 
    authorId: "A0006", authorName: "江戸川困難" 
  }
]
```

2つのリストを引数にとり結合して返却するような関数を書いてみようと思います。なるべく汎用的にしたいのと型チェックもできるようにしたいですね。

# 書いてみる

## 呼び出し方
こんな感じに呼び出して使いたいと思います。

```TypeScript
const booksWithAuthors = innerHashJoin(books, authors, ["id"], ["bookId"])
```

`innerHashJoin()`の引数は左から、結合したいリスト1、結合したいリスト2、結合したいリスト1のキー項目リスト、結合したいリスト2のキー項目リストです。
つまり、SQLで書くと、

```SQL
select * from books join authors on books.id = authors.book_id;
```

のようになります。結合キーがリストを取れるようにしているのはなるべく汎用にしたいので複合キーを想定しているからです。

## シグネチャ
関数シグネチャを考えてみます。

```typescript
function innerHashJoin<LT, RT, LK, RK>(left: LT[], right: RT[], leftKeys: LK[], rightKeys: RK[]): (LT & RT)[]
```

汎用的にするためにジェネリクス型を使います。`LT`は先の例では`Book`に置き換わり、`RT`は`Author`に置き換わります。
`LK`と`RK`はキーのユニオン型を想定していますが、わざわざ型を定義するのも面倒なので`keyof`を使って`LT`と`RT`から導出しましょう。

```typescript
function innerHashJoin
  <LT extends object, RT extends object, LK extends keyof LT, RK extends keyof RT>
  (left: LT[], right: RT[], leftKeys: LK[], rightKeys: RK[]): (LT & RT)[]
```
`keyof`ができるためには`LT`と`RT`は少なくとも`object`ではあるのでついでに`extends`をつけて型を絞り込んでいます。

`LT`が`Book`であるなら`LK`は`keyof Book`のサブタイプでなければならないので、先ほどの例で考えると`LK[]`は`"id"`か`"title"`か`"publishDate"`かを要素にもつリストということになります。`RK`の方も同様です。

最後に戻り値は`LT`と`RT`とに含まれる項目を全て持っているので`&`で型をマージしています。

## 実装してみる

次にJoinの実装をします。`object`はそもそもハッシュテーブルのようなものなのでこれを最大限に利用します。
また、リストの操作にはTypeScriptと相性のいい[Remeda](https://remedajs.com/)を使用します。Remedaは細かく型を指定しなくてもいい感じに型推論してくれて便利です。

まず、インデックステーブルを作ります。性能を考えると小さい方のリストから作る方が良さそうですが今回はそこまでしません。

```typescript
import * as R from "remeda"

function innerHashJoin
  <LT extends object, RT extends object, LK extends keyof LT, RK extends keyof RT>
  (left: LT[], right: RT[], leftKeys: LK[], rightKeys: RK[]): (LT & RT)[] 
{
  const leftAccessor = (row: LT) => R.pipe(
    rows,
    R.pick(leftKeys),
    R.values,
    R.reduce((a, c) => `${a}/${c}`, "") // `/`はキーの区切り文字。キーに`/`が入っていない前提で使用
  )

  // インデックステーブルを作成
  const index = R.groupBy(left, (row) => leftAccessor(row))

  // ...未完成...
}
```

ここで、`leftAccessor()`はリストの1行を取って指定された結合キー項目リストからインデックステーブルのキーを作成する関数です。
今回は単純に値を`/`で結合するようにしました。結合キーの値に`/`が含まれない前提です。例では`B0001`が結合キーなので問題ありません。
今回のようにキーが一つの場合はインデックステーブルのキーは`/B0001`, `/B0002`, ...になります。

インデックステーブルは`groupBy`で作成しています。例では次のようになっている想定です。

```typescript
{
  "/B0001": [{ id: "B0001", title: "2100年のネットワークお悩み相談室", publishDate: "20990301" }],
  "/B0002": [{ id: "B0002", title: "プログラミングの基本を1分でマスターする！", publishDate: "20240101" }],
  "/B0003": [{ id: "B0003", title: "パソコンの電源を入れずにネットの誹謗中傷を消す方法", publishDate: "20380119" }],
  "/B0004": [{ id: "B0004", title: "ロボットたちの休日: AIが作る非常識なバケーションガイド", publishDate: "20240931" }],
  "/B0005": [{ id: "B0005", title: "エイリアンとデバッグ: 異星人から学ぶプログラミングの極意せ", publishDate: "20250301" }],
}
```

同じキーのデータがないので変な感じがしますがこれはこれでOKです。

次に、結合の仕方を考えます。
`left`からインデックステーブルを作成したので結合の元になるのは`right`の方です。`right`をもとに`index`から結合するデータを見つけてくっつけていきます。
フローはこうです。

1. `right`の1行からインデックステーブルを引くためのキーを作成する
2. インデックステーブルから引いた結果が存在するなら、結果のリスト全行を繰り返し`right`の1行とマージする
  a. 結果がない場合は`undefined`にしておく
3. 最後に全ての行をまとめて出来上がり。ただし、`undefined`になっている行は不要なので削除する

早速実装していきます。が、先に1.の部分の1行からインデックステーブルを引くためのキーを作成するのは`left`側でやったので、これを関数に切り出します。

```typescript
import * as R from "remeda"

function createAccessor<T extends object, K extends keyof T>(keys: K[]) {
  return (row: T) => R.pipe(
    rows,
    R.pick(keys),
    R.values,
    R.reduce((a, c) => `${a}/${c}`, "") // `/`はキーの区切り文字。キーに`/`が入っていない前提で使用
  )
}
```

これを使って書き直してみます。

```typescript
// ...前略...

function innerHashJoin
  <LT extends object, RT extends object, LK extends keyof LT, RK extends keyof RT>
  (left: LT[], right: RT[], leftKeys: LK[], rightKeys: RK[]): (LT & RT)[] 
{
  const leftAccessor = createAccessor(leftKeys)
  const rightAccessor = createAccessor(rightKeys)

  // インデックステーブルを作成
  const index = R.groupBy(left, (row) => leftAccessor(row))

  // これは2次元になっている
  const temp = R.map((row) => {
    const key = rightAccessor(row) // 1. キーを作って
    if (key in index) {
      // 2. インデックスにキーがある場合は結果の全行をrightの行とマージする
      return index[key].map(indexRow => ({ ...row, ...indexRow }))
    } else {
      // 2a. キーがないならundefined
      return undefined
    }
  })

  // ...未完成...
}
```

最終的にまとめる前まで書きました。注意して欲しいのはインデックステーブルから引いた結果はリストなので`temp`は二次元になっているということです。
`[[結合した行のデータ], [結合した行のデータ, 結合した行のデータ], undefined, [...]]`のような形になっています。
なので、最終的にはこのリストを`R.flatten`（リストを一次元に）して`R.compact`（undefinedを削除）する必要があります。
これを、`R.pipe`を使って一気に書くとこうなります。

```typescript
// ...前略...

function innerHashJoin
  <LT extends object, RT extends object, LK extends keyof LT, RK extends keyof RT>
  (left: LT[], right: RT[], leftKeys: LK[], rightKeys: RK[]): (LT & RT)[] 
{
  const leftAccessor = createAccessor(leftKeys)
  const rightAccessor = createAccessor(rightKeys)

  // インデックステーブルを作成
  const index = R.groupBy(left, (row) => leftAccessor(row))

  return R.pipe(
    right,
    R.flatMap((row) => {
      const key = rightAccessor(row)
      return key in index ? index[key].map((indexRow) => ({ ...row, ...indexRow })) : undefined
    }),
    R.compact,
  )
}
```

`map`してから`flatten`するのは`flatMap`を使えば一度でできるので書き直しています。

# まとめ
TypeScriptを使って型に気をつけながらオブジェクトのリストを内部結合する関数を書いてみました。
Remedaの恩恵が凄まじいですが型の縛りがありつつ破綻しない程度に汎用的な書き方ができたんじゃないかなと思います。
2つのリスト中に同じキーがあった場合、今回の実装ではインデックステーブル側の値で上書きされてしまうので、SQLで言うところの`as ~~`のように属性名変更の仕組みが必要かもしれません。
また、`object`を使わずに`Map`を使う実装の方が本格的かもしれません。