TypeScript型システムで遊ぼう

はじめに

こんにちは。C++大好き風露さんです。ポンポさんのアニメ映画化決定しましたね¹。楽しみです。小泉さんは読んでいません²。

さて、今回は残念ながらC++の話ではなく³TypeScriptです。
C++の柔軟な型システムは柔軟すぎて訳のわからない黒魔術が蔓延っていることで有名^[要出典]ですが、TypeScriptも頑張ればいろんなことができます。
この記事の目的はそんなTypeScriptの型で遊ぶことです。役に立つかどうかは考えません。そのつもりでよろしくお願いします。

なお今回の記事を書くに当たり、 @uhyo 氏のTypeScriptで最低n個の要素を持った配列の型を宣言する方法を大いに参考にさせていただきました。私の記事で多用している根幹のアイディアは自分では思い付けませんでした。この場を借りてお礼申し上げます。

まずは何かと役に立つやつ

Prepend<T, U>

これはほとんど uhyo 氏の記事からのコピーですが、タプル型の先頭に新しく要素を追加するメタ関数です。

type Prepend<T extends unknown[], U = unknown> =
  ((u: U, ...t: T) => void) extends ((...v: infer V) => void) ? V : never;

Prepend<T extends unknown[], U> = [U, ...T] のような記法があれば良かったのですが、これが不可能なので関数型のシグネチャを経由することで実装する、というアイディアですね。これを初めて見たときは目からウロコでした。
ちなみに、 U にデフォルト引数を付けているのは以下で Prepend<T> などと書けると便利だからです。

Append<T, U>

uhyo 氏の記事 では Append と呼ばれていたものをわざわざ Prepend にしたのは、 Append は末尾に追加するものという固定観念があったからです。実際DOMの ParentNode.append() と ParentNode.prepend() などはこの形式なので、対称性を持たせたかった。
上記のように Prepend は関数型を経由することで定義できますが、 Append は同じようにはできません。(...t: T, u: U) => void のような書き方ができないからです。
なので、発想を変えてみます。

タプル型 T の末尾に U を挿入するには、Tより長さが一つ大きいタプル型を作る必要があります。
このようなタプル型は既に用意した Prepend を使えば作れます。もちろんキーに対応する値型は求めているものとは異なるのですが、必要なキーはそろっていることが重要です。キーが揃えば mapped type が使えます。

TypeScript の mapped type の挙動はクセがあって、

type X = { [K in keyof any[]]: any[][K]; }

などと書くと愚直に any[] のキーを全部列挙する上に Symbol.iterator などの well-known symbol を列挙してくれない（！）せいで、この例だと X と any[] は異なる型になるのですが、

type X<T> = { [K in keyof T]: T[K]; }
type Y = X<any[]>

などのようにジェネリクスの引数を経由すると、配列やタプルの場合はインデックスだけがキーとして列挙されて、同じキーを持つ配列やタプルが作られ、この例だと Y と any[] が同じ型になります。ふしぎな挙動だ……。
このような挙動に対応するため、 Prepend<T> から直接キーを列挙するのではなく、別のジェネリクスを経由し、

type AppendImpl<T extends unknown[], U, V extends unknown[]> = /* ... */;
type Append<T extends unknown[], U = unknown> = AppendImpl<T, U, Prepend<T>>;

とします。後は AppendImpl の中身を実装すれば良いのですが、 V に含まれるキーのうち、 T に含まれる場合は T の対応する値型を使い、それ以外の場合は U にすると、 最後のキーだけを U にすることができます。これをそのままコードで表すと、

type AppendImpl<T extends unknown[], U, V extends unknown[]> = {
  [K in keyof V]: K extends keyof T ? T[K] : U;
};
type Append<T extends unknown[], U = unknown> = AppendImpl<T, U, Prepend<V>>;

となります。

論理演算色々

Extends<T, U>

T が U の派生型であれば true に、そうでなければ false になるメタ関数です。まあ説明せずともだいたい分かると思いますが、

type Extends<T, U> = T extends U ? true : false;

基本はこれだけです。……と言いたいところなのですが、一つ問題があって、これを使うと、

type _ = Extends<'a' | 'b', 'a'> // => boolean

ユニオン型はジェネリクスの引数を経由すると分解されてそれぞれに適用した後にもう一度ユニオン型としたような挙動を示すことがあります。この例だと、 Extends<'a', 'a'> は true で、 Extends<'b', 'a'> は false になるので、最終的に true | false つまり boolean となってしまいます。
ここらへんの挙動は私自身よく理解していないのですが、これを回避することも可能で、

type Extends<T, U> = (T extends U ? true : false) extends true ? true : false;

のようにすると、 Extends<'a' | 'b', 'a'> のような型でも false になります。この場合、一回目の条件型で true や false を経由する必要もないので、

type Extends<T, U> = (T extends U ? 1 : 0) extends 1 ? true : false;

のようにしても大丈夫です。

Not<T>

論理を反転します。 T に代入できる型は true か false に限りたいところですが、 true | false であるところの boolean 型も代入できてしまいます。仕方ありませんが、無視します。 boolean に対して boolean を返すことも不可能ではありませんが、めんどくさい。

type Not<T extends boolean> = Extends<T, false>;

このように書くと、 T = false の時は true 、 T = true の時は false が返ります。 boolean の場合は false になります。

Conjunction<T>

論理積（連言、合接とも）です。 T = [T1, T2, T3, ..., Tn] のようなタプル型で、 T1 && T2 && T3 && ... && Tn のような計算をしたい。言い換えると、タプル型の全ての要素が true であった時だけ true を返したい。

ところで、 TypeScript の配列型（タプル型含む）に number でアクセスすると、配列の全ての要素型のユニオン型が得られます。つまり、 T = [true, false, true] なら T[number] は true | false | true = true | false = boolean であり、 [false, false, false] なら false | false | false = false となる訳です。もうお分かりですね。 T[number] の型が true になるのは、全ての要素型が true である時だけです。それ以外の場合は boolean もしくは false です。以上を踏まえると、

type Conjunction<T extends boolean[]> = Extends<T[number], true>;

となります。
ちなみに、 T = [] の時は T[number] = never となるわけですが、 Extends<never, true> は true となります。
論理積の計算を true && T1 && T2 && ... && Tn と考えると、空の時は true になるのは理に適っています。C++でも演算子が && の時の 単項 fold expression で、パラメーターパックが空の時は true になるとなっていますし。

Disjunction<T>

論理積があれば論理和（選言、離接）もある。というわけで、これはもうお分かりですね、 T[number] が false の時は false、それ以外は true です。

type Disjunction<T extends boolean[]> = Not<Extends<T[number], false>>;

IsSame<T, U>

T と U が同一の型かどうかを確かめます。同一の型となる条件は、 T が U を継承し、 U が T を継承していることとします。

type IsSame<T, U> = Conjunction<[Extends<T, U>, Extends<U, T>]>

ちなみに、この判定方法は弱点があって、例えば、

type A = { 0 : 0 };
type B = { '0' : 0 };
type C = IsSame<A, B>;

とすると、 C は true になります。 TypeScript の型システム上、厳密には A と B は異なる型（ keyof A が 0 になるのに対して、 keyof B は "0" になる）なのですが、実際 JavaScript の世界ではキーが数値型か文字列型かを区別しないので、それに合わせてか TypeScript でも A 型の値は B 型の変数に代入できるし、その逆も可能です。
厳密にそこら辺のチェックをしようと思ったら keyof T と keyof U の比較をすればいいので、

type IsSame<T, U> = Conjunction<[
    Extends<T, U>, Extends<U, T>,
    Extends<keyof T, keyof U>, Extends<keyof U, keyof T>,
]>;

とかやっても良いのかもしれませんが。

四則演算

TypeScriptのリテラル型で四則演算をしたい。TypeScriptに触れたことのある人なら誰でも一度は思うことでしょう^[要出典]。
タプル型の length が自然数のリテラル型になりうる事を利用できないかと考え、タプルの要素を増やす方法が分からなかったのですが、 uhyo 氏の記事 を見ることでようやく蒙を啓かれました。

Add<M, N>

早速加算から実装しましょう。
考え方はこうです。

M, N の2つの自然数リテラルを加算することを考えます。空のタプル型 T, U, V を用意し、以下の操作を繰り返します。

• T['length'] が M でなく、かつ U[length] が N でないとき、T = Prepend<T>, U = Prepend<U>, V = Prepend<Prepend<V>> とする
• T['length'] が M かつ U[length] が N でないとき、U = Prepend<U>, V = Prepend<V> とする
• T['length'] が M でなく、かつ U[length] が N のとき、T = Prepend<T>, V = Prepend<V> とする
• T['length'] が M かつ U[length] が N のとき、 Vの長さ を返す。

要するに、「要素数がMに到達するまで要素数を増やし続けるタプル T」「要素数が N に達するまで要素数を増やし続けるタプル U」「片方の要素数が増えたときは要素数を1つ増やし、両方の要素数が増えたときは要素数を2つ増やすことで、 T と U の要素数の合計分の要素を持つタプル V」を用意する訳です。

これを踏まえて、実装はこのようになります。

type AddImpl<
  M extends number,
  N extends number,
  T extends unknown[],
  U extends unknown[],
  V extends unknown[]
> = {
  0: V;
  1: AddImpl<M, N, T, Prepend<U>, Prepend<V>>;
  2: AddImpl<M, N, Prepend<T>, U, Prepend<V>>;
  3: AddImpl<M, N, Prepend<T>, Prepend<U>, Prepend<Prepend<V>>>;
}[
  T extends { length: M } 
    ? U extends { length: N } ? 0 : 1
    : U extends { length: N } ? 2 : 3
];
type Add<M extends number, N extends number> =
     AddImpl<M, N, [], [], []> extends { length: infer T } ? T : never;

Sub<M, N>

減算も加算とほぼ同じような考え方で行うことができます。
加算と異なるのは、 V の増やし方です。 M - N (N <= M) を考えるとして、 U のサイズが N 以下の時は加算と異なり V を増やさないようにすることで、 T のサイズが M 未満で U のサイズが N に到達している時だけ V が増えるようになります。

type SubImpl<
  M extends number,
  N extends number,
  T extends unknown[],
  U extends unknown[],
  V extends unknown[]
> = {
  0: V;
  1: SubImpl<M, N, Prepend<T>, U, Prepend<V>>;
  2: { length: never }; // M < N なので負の数になるが、負の数の数値リテラルを自動生成する方法が見つからないので never にしておく 
  3: SubImpl<M, N, Prepend<T>, Prepend<U>, V>;
}[
　U extends { length: N }
    ? T extends { length: M } ? 0 : 1
    : T extends { length: M } ? 2 : 3
];
type Sub<M extends number, N extends number> =
     SubImpl<M, N, [], [], []> extends { length: infer T } ? T : never;

Mul<M extends number, N extends number>

乗算も同じような感じで、 T, U, V を増やすやり方を変更すれば可能です。乗算の場合は V を M 回増やす操作を N 回繰り返すと考えればいいので、

• T のサイズが M になるまで T と V を増やす
• T のサイズが M だったら、 U のサイズを増やして T を空にする
• U のサイズが N になるまで上記操作を繰り返す

という処理で V のサイズを M * N にすることができます。

type MulImpl<
  M extends number,
  N extends number,
  T extends unknown[],
  U extends unknown[],
  V extends unknown[]
> = {
  0: V;
  1: MulImpl<M, N, [], Prepend<U>, V>;
  2: MulImpl<M, N, Prepend<T>, U, Prepend<V>>;
}[U extends { length: N } ? 0 : T extends { length: M } ? 1 : 2];
type Mul<M extends number, N extends number> =
     MulImpl<M, N, [], [], []> extends { length: infer T } ? T : never;

Div<M, N>

最後に除算です。 number 型は浮動小数点ですが浮動小数点リテラルを自動生成する術はないので、小数点以下切り捨ての演算になります。
やり方は、 T のサイズが M になるまで T と U を増やし、 U のサイズが N になる度に V を増やして U を空にするという処理を行います。

type DivImpl<
  M extends number,
  N extends number,
  T extends unknown[],
  U extends unknown[],
  V extends unknown[]
> = {
  0: V;
  1: DivImpl<M, N, T, [], Prepend<V>>;
  2: DivImpl<M, N, Prepend<T>, Prepend<U>, V>;
}[T extends { length: M } ? 0 : U extends { length: N } ? 1 : 2];
type Div<M extends number, N extends number> =
     DivImpl<M, N, [], [], []> extends { length: infer T } ? T : never;

除算とほぼ同じ方法で、剰余も求めることができます。これは読者への宿題とする。なんて。いや、本当に除算をちょっと変えるだけなので、すぐに作れると思います。

さあ、ここまでで四則演算が実装できました。
ただ、このやり方は型の再帰深度にすぐに引っかかってしまうので、せいぜい40回程度が限界です。 Add<40, 41> で81までは作ることができるのを確認しましたが、Add<41, 41> だとエラーが出るとかそういうレベルです。再帰回数が多いとすぐ限界にひっかかるので、うまく再帰を減らしてやればもう少し範囲を広げることができるかもしれません。
数を大きくすると再帰深度が線形に増えるので、対数にできないかとか考えてみましたが、今の所思いつきません。何かいい方法を見つけたらコメントとかで教えてもらえると嬉しいです。

タプル操作あれこれ

先程の Prepend や Append の応用で、配列を色々操作することもできます。

RemoveFirst<T>

Prepend とは逆に、先頭の要素を削除します。実装は Prepend と大体同じやり方を使います。

type RemoveFirst<T extends unknown[]> =
  ((...t: T) => void) extends ((_:infer _, ...u: infer U) => void) ? U : never;

RemoveLast<T>

末尾から削除する版も。例によって関数型を経由する方法は使えないので、 Append と同じような方法を使います。

type RemoveLastImpl<T extends unknown[], U extends unknown[]> = {
  [K in keyof U]: K extends keyof T ? T[K] : never;
};
type RemoveLast<T extends unknown[]> = RemoveLastImpl<T, RemoveFirst<T>>;

ReverseSequence<N>

[..., 3, 2, 1, 0] みたいな配列を作るメタ関数です。
サイズが N に達するまで、タプルの length をタプル自身の先頭に挿入していくことで可能です。

type ReverseSequenceImpl<N extends number, T extends unknown[] = []> = {
  0: T;
  1: ReverseSequenceImpl<N, Prepend<T, T['length']>>;
}[T extends { length: N } ? 0 : 1];
type ReverseSequence<N extends number> = ReverseSequenceImpl<N>;

IndexSequence<N>

[0, 1, 2, 3, ...] みたいな配列を作るメタ関数です。

ReverseSequence と同じように Append を使って……と考えていましたが、 Append を使うと極端に再帰回数が少なくなってしまうので、考えを変えることにしました。
ReverseSequence で生成したタプルの値は、先頭が length - 1 で末尾が 0 です。そして、タプルのインデックスは先頭が 0 で末尾が length - 1 です。 一般化すると、 K 番目のインデックスの値は length - 1 - K で、 length - 1 - K 番目の値は K です。つまり、 T[T[K]] = K が成り立ちます。ですから、そのようなmapped typeを書いてしまえば良いわけです。
そもそも、 ReverseSequence より先に IndexSequence を作ろうとしたのですが、この方法を使う以上、 ReverseSequence を先に作ったほうが都合がいいので先に持ってきました。

type IndexSequenceImpl<T> = {
  [K in keyof T]: T[K] extends keyof T ? T[T[K]] : never;
};
type IndexSequence<N extends number> = IndexSequenceImpl<ReverseSequence<N>>;

ちなみに、適当に長さNのタプルを作って [K in keyof T]: K でインデックスを取り出せばいいのでは、と思うかもしれませんが、タプルのインデックスは実は数値型リテラルではなく文字列型リテラルになっているので、それをやると ['0', '1', '2', ...] になってしまいます。

Reverse<T>

先程の IndexSequence は、 ReverseSequence の値の並びを反転する方法で作成したとみなせます。 ReverseSequence 以外のタプルであっても、同じような方法で反転することが可能です。

type ReverseImpl<T, U> = {
  [K in keyof U]: U[K] extends keyof T ? T[U[K]] : never;
}
type Reverse<T extends unknown[]> = ReverseImpl<T, ReverseSequence<T['length']>>;

Head<T, N>

タプルの先頭から N 要素を取り出します。長さが N の配列さえあれば、mapped typeを使えます。

type HeadImpl<T, U> = {
  [K in keyof U]: K extends keyof T ? T[K] : never;
};
type Head<T extends unknown[], U extends number = 1> = HeadImpl<T, ReverseSequence<U>>;

Tail<T, N>

Head の逆です。 タプルの N 番目から後ろの要素を取り出します。 mapped type でやる方法はちょっと思いつかないので、再帰でやります。

type TailImpl<T extends unknown[], N extends number, U extends unknown[] = []> = {
  0: T;
  1: TailImpl<RemoveFirst<T>, N, Prepend<U>>;
}[U extends {length: N} ? 0 : 1];
type Tail<T extends unknown[], N extends number = 1> = TailImpl<T, N>;

Slice<T, M, N>

Head と Tail があれば Slice を作れます。 タプル T の M 番目から N 要素を取り出します。

type Slice<T extends unknown[], M extends number = 0, N extends number = 1> =
  Tail<T, M> extends infer U ? U extends unknown[] ? Head<U, N> : never : never;

終わりに

まだいくつかネタは残っているような気はしますが、そろそろ疲れてきて最後の方説明がおざなりになったのでここらで終わります。
またそのうちやる気が出てきたら続きでも書こうかと思います。それでは。

1. 『映画大好きポンポさん』一時期話題になったから知ってる人も多いだろうけど面白いので全人類見て。2とスピンオフのフランちゃんも面白いよ。 ↩

2. 『ラーメン大好き小泉さん』のこと ↩

3. 自分でテーマを選んでおいて残念も何もないが ↩