はじめに

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

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

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

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して次のような出力を得たいとします。

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

書いてみる

呼び出し方

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

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

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

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

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

シグネチャ

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

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から導出しましょう。

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を使用します。Remedaは細かく型を指定しなくてもいい感じに型推論してくれて便利です。

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

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で作成しています。例では次のようになっている想定です。

{
  "/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から結合するデータを見つけてくっつけていきます。
フローはこうです。

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

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

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}`, "") // `/`はキーの区切り文字。キーに`/`が入っていない前提で使用
  )
}

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

// ...前略...

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を使って一気に書くとこうなります。

// ...前略...

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を使う実装の方が本格的かもしれません。