TypeScriptで型レベル演算

# はじめに

こちらは[長野高専 Advent Calendar 2021](https://qiita.com/advent-calendar/2021/nnct)の3日目の記事です。前日は @yabanui さんの｢[Fusion360で基板設計～第2回「ライブラリーをつくろう②」～](https://moyoi-memo.hatenablog.com/entry/2021/12/02/204432)｣でした。僕には回路分野はさっぱりですね…

さて、皆さんTypeScriptは使いますか？今やTypeScriptはJavaScriptの代替言語としてWebフロントエンドだけではなく、広い分野で使われています。
TypeScriptの特徴として型の表現力の高さが挙げられます。動的型付け言語の中でもかなり型がゆるい方であるJavaScriptにどうにかして型を当てるためにTypeScriptには他の言語には無い、ユニークな型がたくさんあります。

結果として、TypeScriptの型はチューリング完全です。[^1]つまりTypeScriptの型だけでかなり色々な事ができるわけです。

[^1]: とはいえTypeScriptの型には再帰上限とインスタンス化の上限があり、再帰上限は50とかなり低く設定されているため、複雑なことをするとすぐに再帰上限に引っかかります。

ということで今回はTypeScriptの型で加算減算とそれを用いたRange型の実装をしてみたいと思います。

なお、今回実装したコードは[このGist](https://gist.github.com/shun-shobon/ca7577f3fa1f7ec317ac3f31a97a5858)に上がっていますので、詳しく見たい方は参照してください。

# 自然数型の定義

加算減算を実装するにもそもそも数を表す型がありません。まずは自然数型を定義してみましょう。自然数の表現はタプルを使い、数の大きさをタプルの長さで表現してみます。

```typescript
// 自然数型
type Nat = unknown[];

// 以下は全てNatと継承関係にある(T extends Natが成り立つ)
type Zero = [];                 // 長さ0のTuple
type One  = [unknown];          // 長さ1のTuple
type Two  = [unknown, unknown]; // 長さ2のTuple
// ...
```

これだけではただ長さ`N`のタプルを定義しただけで、それぞれの自然数型に関係性がありません。そこで、与えられた自然数型の次の値を返す型を作ってみます。自然数は[ペアノの公理](https://ja.wikipedia.org/wiki/%E3%83%9A%E3%82%A2%E3%83%8E%E3%81%AE%E5%85%AC%E7%90%86#%E5%AE%9A%E7%BE%A9)によると、

> ペアノの公理は以下の様に定義される。
> 
> 自然数は次の5条件を満たす。
> 
> 1. 0は自然数である。
> 2. 任意の自然数 a にはその後者 (successor)、suc(a) が存在する（suc(a) は a + 1 の "意味"）。
> 3. 0 はいかなる自然数の後者でもない（0 より前の自然数は存在しない）。
> 4. 異なる自然数は異なる後者を持つ：a ≠ b のとき suc(a) ≠ suc(b) となる。
> 5. 0 がある性質を満たし、a がある性質を満たせばその後者 suc(a) もその性質を満たすとき、すべての自然数はその性質を満たす。

だそうです。今回はこの2番目の条件

> 任意の自然数 a にはその後者 (successor)、suc(a) が存在する（suc(a) は a + 1 の "意味"）。

を使います。要は与えられた`Nat`型の長さを`+1`して返せばよさそうですね。これはTypeScript 4.0で導入されたVariadic Tuple Typesを使えば簡単に実装できます。

```typescript
type Suc<N extends Nat> = [...N, unknown];
```

この`Suc<N>`に`[]`を渡せば`[unknown]`が返ってきますし、`[unknown]`を渡せば`[unknown, unknown]`が返ってきます。これで｢任意の自然数の一つ後ろの数｣を表現できるようになりました。

## 加算･減算

加減算はどのように実装すればよさそうでしょうか？自然数をタプルの長さで表現しているので与えられた2つのタプルの長さを合わせれば加算は実装できそうです。実はこれもVariadic Tuple Typesを使えば簡単です。

```typescript
type Add<N1 extends Nat, N2 extends Nat> = [...N1, ...N2];
```

減算は少し難しいですが、同じように実装できます。先にコードを示します。

```typescript
type Sub<N1 extends Nat, N2 extends Nat> = N1 extends [...N2, ...infer Ans] ? Ans : Zero;
```

`N1`が`N2`よりも長い(つまり`N1`の方が大きい数)とき、`N1 extends N2`が成り立ちます。ここで`infer`キーワードを使えば`N1`が`N2`よりもどれだけ大きいかを型としてキャプチャできます。`[...N2, ...infer Ans]`とすることで`N2`からはみ出た`unknown`を配列としてキャプチャし、それを`Sub<N1, N2>`の結果として返すことで減算が実装できます。なお、`N2`の方が大きい場合は`N1 extends N2`が成り立たないため`Zero`が返ります。[^2]

[^2]: 本当は`Zero`よりも`never`を返したほうがいいのかもしれませんが、今回は`Zero`にしています。

# リテラル型との相互変換

次にリテラル型との相互変換を実装してみましょう。リテラル型はTypeScript特有の型で、数値や文字列などのリテラルを直接型として使うことができます。

## `Nat`型→リテラル型

ということで先程作った`Nat`型からリテラル型への変換を実装してみます。`Nat`型→リテラル型はかなり簡単に実装できます。

```typescript
type NatToNum<N extends Nat> = N["length"];
```

TypeScriptでは`T[K]`と書くと`T`の`K`プロパティを型として取得できます。タプルは`Array`を継承しているので`length`プロパティを持ちます。`Array`の場合`length`プロパティの型は`number`になりますが、タプルの場合は`number`のリテラル型として取得できます。結果的に`N["length"]`とするだけで簡単にリテラル型へ変換できます。

## リテラル型→`Nat`型

さて次はリテラル型→`Nat`型ですが、これは少々面倒です。というのも一発でリテラル型を`Nat`型に変換する手段がありません。
ここで再帰の力を借ります。`Nat`型→リテラル型はすでに実装済みなので、

1. `[]`(0)の`Nat`型を用意
1. `Nat`をリテラル型に変換
1. 与えられたリテラル型と等しいか確認
1. 等しかったらその時の`Nat`が答え
1. 等しくなかったら`Nat`を1増やす
1. 2に戻る

これでリテラル型→`Nat`型が実装できます。何はともあれコードを見てみましょう。

```typescript
type _NumToNat<L extends number, TNat extends Nat> = NatToNum<TNat> extends L ? TNat : _NumToNat<L, Suc<TNat>>;
type NumToNat<L extends number> = _NumToNat<L, Zero>;
```

まず`_NumToNat<L, TNat>`ですが、これは先程の手順の2〜6を行っています。リテラル型は派生型が無いため、`T`がリテラル型の場合、`T extends U`は`T`と`U`が等しい値のときのみ成立します。`NatToNum<TNat> extends L`が成立する場合はその時の`TNat`を返し、等しくない場合は`TNat`を`Suc<N>`で1増やして再帰しています。
`NumToNat<L>`は`_NumToNat<L, TNat>`に`L`と初期値の`Zero`を渡しているだけです。

# `Range`を作ってみる

ここまで実装してきた自然数とリテラル型との相互変換を用いて、｢`S`から`L`までのタプル｣を作る`Range`型を作ってみましょう(つまりPythonの`range`関数みたいなのを作ります)。と言っても`Range`は`dom.d.ts`にすでに存在しているため名前は`Range_`にします。

```typescript
type _Range<
  F extends Nat,
  L extends Nat,
  I extends Nat,
  Ans extends unknown[],
> = I extends Sub<L, F> ? Ans : _Range<F, L, Suc<I>, [...Ans, NatToNum<Add<F, I>>]>;
type Range_<F extends number, L extends number> = _Range<NumToNat<F>, NumToNat<L>, Zero, []>;
```

ちょっと複雑ですが、まずは`_Range<F, L, X, Ans>`から見ていきましょう。
`F`、`L`はそれぞれ開始値と終了値の`Nat`型です。そして`I`は現在どこまでカウントしたかを保持するカウンタです。`Ans`は最終的な答えのタプルを保持しています。
まず`I extends Sub<L, F>`ですが、数え上げが終了したかどうかを判定しています。`Sub<L, F>`で求めたいタプルの長さが求まるので`I`がそれに達しているかどうかが個々で判定できます。この条件を満たしている場合はそのときの`Ans`が答えになっているので`Ans`をそのまま返します。

さて条件を満たしていないときの処理ですが、`_Range<F, L, I, Ans>`に`F`と`L`はそのまま、`I`は1増やしたものを、`Ans`は末尾に現在の`I`と`F`を足したものを追加して渡しています。

`Range_<F, L>`は与えられたリテラル型を`Nat`型に変換して、`I`と`Ans`には初期値を渡しています。

ちなみに`Ans`は`number[]`であることが自明なのですが、`number[]`にすると何故かTypeScriptがエラーを吐きます。どうやらNatToNumの型が`number`であることを推論できていないようですが、詳しいことはよくわかりません。直せる方がいたら編集リクエストをお願いします。
![`number[]`で何故かエラーを吐くTypeScript](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/628629/5b4e2447-2a32-d87e-27c3-f532cd25bdee.png)

これで`Range`型が完成しました！あとはここに好きな数値リテラル型を入れてあげれば使えます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/628629/cd38a8bc-b039-1184-b191-f354083b77ec.png)

# 最後に

TypeScriptの型は非常に強力で、型レベルで様々な事ができます。今回は使いませんでしたが、`Template Literal Type`を使えば型レベルでSQLやGraphQLのパーサを作ることもできるようです。皆さんもTypeScriptのユニークな型を使って面白い型を作ってみましょう！

なお、TypeScriptの型の力を鍛えたい場合は[Type Challenge](https://github.com/type-challenges/type-challenges)というリポジトリの問題を解いてみることをおすすめします。

明日の記事は @Shibaken_8128 の｢論理式簡略化アルゴリズムを実装｣です。どんな記事なのか楽しみですね！

それでは良いTypeScriptライフを！