TypeScriptの型を使ってリストのソートしてみた

前回はTypeScriptの型で数値の演算を定義してFizzBuzzやフィボナッチ数を導出しました。
減算を使えば数値の比較演算を定義できるので、数値の比較とリスト操作を定義して型で関数型の入門書でよく扱われる(エセ?)クイックソートを実装したいと思います。今回はこちらの記事に影響されているかなと思います。

数値演算

今回は使用するのは減算のみ。

type NumberToTuple<T extends number, U extends unknown[] = []> = U['length'] extends T ? U : NumberToTuple<T, [...U, unknown]>
type Sub<T extends number, U extends number> = NumberToTuple<T> extends [...NumberToTuple<U>, ...infer S] ? S['length'] : never

比較演算

=,<,<=,>,=を定義します。

type Eq<T, U> = T extends U ? (U extends T ? true : false) : false
type LT<T extends number, U extends number> = Sub<T, U> extends never ? true : false
type LE<T extends number, U extends number> = Sub<T, U> extends 0 ? true : LT<T, U>
type GT<T extends number, U extends number> = LE<T, U> extends true ? false : true
type GE<T extends number, U extends number> = LT<T, U> extends true ? false : true

リスト操作

Tailしか使わないけど、関数型のリスト操作の基本のHeadも。

type Head<T extends unknown[]> = T extends [] ? never : T[0]
type Tail<T extends unknown[]> = T extends [] ? never : T extends [unknown] ? [] : T extends [unknown, ...infer U] ? U : never

ソート

ソート本体が長くなってしまうので、リストから特定の数値以上の数値のリストを返す型と特定の数値未満の数値のリストを返す型を定義します。

type GEList<T extends number[], Pivot extends number> = T extends [] ? [] : GE<T[0], Pivot> extends true ? [T[0], ...GEList<Tail<T> extends number[] ? Tail<T> : [], Pivot>] : GEList<Tail<T> extends number[] ? Tail<T> : [], Pivot>
type LTList<T extends number[], Pivot extends number> = T extends [] ? [] : LT<T[0], Pivot> extends true ? [T[0], ...LTList<Tail<T> extends number[] ? Tail<T> : [], Pivot>] : LTList<Tail<T> extends number[] ? Tail<T> : [], Pivot>

これらのフィルタを使うと下記のように定義できる。

type QuickSort<T extends number[]> = T extends [] ? [] : [...QuickSort<LTList<Tail<T> extends number[] ? Tail<T> : [], T[0]>>, T[0], ...QuickSort<GEList<Tail<T> extends number[] ? Tail<T> : [], T[0]>>]

type SoredList = QuickSort<[1, 4, 2, 5 ,3 ,7 ,6 ,1, 3]>

さいごに

四則演算と比較演算を定義すれば後は普通にアルゴリズムを実装するだけという感じ。
簡単に型での数値計算が実装できるのは固定長配列型のlengthと数値リテラル型のおかげです。
型とTypeScript面白いなぁ。