TypeScriptで、プログラムを動かさず型定義だけで足し算の結果を得たい選手権

TypeScriptでは静的型定義を使うことで、変数に予期せぬ値が入ってこない事を保証できます。

ですが、当たり前ですがそれ以上の事はできません。

例えば下記のプログラム

```ts
type One    = number;
type Two    = number;
type Three  = number;
type Four   = number;

const three: Three = 3;

const valA: Two   = three; // エラー出ない
const valB: Three = three;
const valC: Four  = three; // エラー出ない
```

上記のプログラムでは`Two`や`Four`といった型に`Three`型の値を代入しています。一見間違っているようですが、当然すべて`number`型に含まれているためコンパイル時の型エラーは特になにも出ない、いたって正しいプログラムです。それが普通です。
「1 + 2 が3なのかどうか」といった演算の結果を確かめるのは型定義ではなくテストコードの役割だと思います。

ですが、こういった演算の結果を、型定義だけを使って確かめる事はできないかと思いました。そこで「TypeScriptでプログラムを動かさず、型定義だけで足し算の結果を得る」ことはできないか、試してみました。

TypeScriptの静的型付けだけでどこまで「プログラムの正しさ」を表現できるのか、すこし見てみましょう。

## 環境
- TypeScript 3.5.1
    - [TypeScript playground](http://www.typescriptlang.org/play/index.html)を利用

## レギュレーション
- 下記によって「数」を再帰的に定義
    - 加法単位元(零元)を定義
    - Aが「数」n であるときの、 n + 1 を定義
- 「数」a, b が「同値」である関係 a = b を定義

以上によって定義した「数」と「同値」を、TypeScriptの型で表現します。

定義した型を使って「1 + 2 = 3」[^1]が正しく、「1 + 2 = 2」[^1]と「1 + 2 = 4」[^1]が誤りであることを、TypeScriptのプログラムを動かさずに型定義のエラーによって示すことを目指します。

ここで言う型定義のエラーとは、TypeScriptをStrict Modeでコンパイルできないこと([TypeScript playground](http://www.typescriptlang.org/play/index.html)でAlways Strictを有効にし、赤の波線が表示されること)とします。

[^1]: 本稿では任意のa, bに対する演算a+bを定義していないため、実際には「1 + 2」を表現することはできず「((0 + 1) + 1) + 1」と表現することになる

## アプローチ1: 次元数風の定義
- 0 := ∅ (空集合)
- 1 := [∅]
- 2 := [[∅]]
- 3 := [[[∅]]]

のように、集合の次元数を「数」と定義してみます。

```ts
// 零元を空集合
type Zero = null;
// Aが「数」nであるとき、n + 1 は [A]
type Increment<T> = [T];
```
AとBが「同値」であることの定義は「型Aに型Bが代入できる」とします。

数の定義はこんなかんじになります。

```ts
type One    = [null];
type Two    = [[null]];
type Three  = [[[null]]];
type Four   = [[[[null]]]];
```

下記のように定義しても同様です。

```ts
type One    = Increment<Zero>;
type Two    = Increment<One>;
type Three  = Increment<Two>;
type Four   = Increment<Three>;
```

実際の演算はこんな感じです。

```ts
function plusOne<T>(val: T): Increment<T> {
  return [val];
}

const zero: Zero = null;
const one: One = plusOne(zero);
const two: Two = plusOne(one);

const result = plusOne(two);
const valA: Two   = result; // Error
const valB: Three = result;
const valC: Four  = result; // Error
```

無事に2と4で型定義のエラーが出て、答えが3であることが確認できました。

プログラムを動かさなくても、演算の結果が正しいかどうかを型エラーで検知することができました。

[TypeScript playground でエラーを見る](http://www.typescriptlang.org/play/#code/PTAEje0xhRUJIZC8vQxtMBAqAoALgTwA4FNQC1sAnAe1AF5QA7AVwBtaBuZEUAQUBkGQGAZAHU0FgGSwOYMgIQZA0QyALBkCyDIEAGSqADUoAIzlQAbVYBdNFlwBJSgGNC2ALbZKqADwAVAHwrV1jU205QAeUq5QPiqpr0zq641gDupD4O-nS0GkEYbtYAFsbefqrRgXFMCbgAYsTUhJHpGQGxcUHIAGbUhqgAlsSymLTUAM6e2Da2ABQAbgCGtABcoNYAlGP6RqbmVnagAN7IPsaoRbKqQ7FMAL7IyAbN7aigAF5ExGMEJCrlTMeUp6DN2GNdKq0dXb2XJBNHiczqhwmMwqQKN9Ol5em9AYcni9jO06GcoW0YdheqDiAikWcdqxweESqAUWiGKAWABRQgkQhHYGgHYAIXBKWwuAoFNoqCBz0JwwAwmMCkVfOTsKi+VTafTiIygA)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/50391/4e49c903-59ee-0922-f5e9-0dad47d218b3.png)

赤の波線でエラーがしめされています。

## アプローチ2: 順序数風の定義
- 0 := ∅ (空集合)
- 1 := [∅]
- 2 := [∅, [∅]]
- 3 := [∅, [∅], [∅, [∅]]]

のように、順序数の定義のような集合を用意し、これを「数」としてみます。

```ts
// 零元を空集合
type Zero = never;
// Aが「数」nであるとき、n + 1 は A ∪ [A]
type Increment<T> = T | [T];
```
この時、AとBが「同値」であることの定義は、(A∪B)⊆(A∩B)とします。

```ts
type Equal<T,U> = T | U extends T & U ? any : never;
```
数の定義はこんな感じ。

```ts
type One    = [never];
type Two    = [never] | [[never]];
type Three  = [never] | [[never]] | [[[never]]];
type Four   = [never] | [[never]] | [[[never]]] | [[[[never]]]];
```

実際の演算は、こんな感じです。

```ts
// 1 + 1
type OnePlusOne = Increment<Increment<Zero>>;
// 2 + 1
type Result = Increment<OnePlusOne>;

const valA: Equal<Result, Two> = null;   // 2 + 1 = 2: Error
const valB: Equal<Result, Three> = null; // 2 + 1 = 3
const valC: Equal<Result, Four> = null;  // 2 + 1 = 4: Error
```

こちらも無事に型エラーを出し、演算結果が3であると得ることができました。

同値の定義がちょっと冗長なものの、ほとんどを型で表現できておりJavaScriptにコンパイルすると最後の3行しか残らないのがきれいです。

[TypeScript playgroundでエラーを見る](http://www.typescriptlang.org/play/#code/PTAEje0xhRUJIZC8vQxtMBAqAoALgTwA4FNQC1sAnAe1AF5QA7bANyIG5kRQBBQGQZAYBkAdTQWAZLBzBkBCDIGiGQBYMgWQZAgAyVQAalABGcq1CAqIlABtFgF00WXAElKAY0LYAttkqoAPABUAfMrugAPprvbGenKACiAI4ArgCGADb2ADQAqk4ULu7RoNgAHqhWACYAzqAuAGSgSQD8oCGU6KAAXFS0DMg+uADy1KCtyhrUdIReDbkA7qRtFB213W6aI13aPRi+dgAWZrjtnUTa4xqTa+vum1vd04yzuABixEGEQ5qrY7v70xubN9M7E0+jLz1MYEryCr3NbAABTCQSygOURlMFistihZks1hsBBIDgcjGYACY5IpegAlbBZIJhVCQkwI2E2QEgsGA9H1YzEShZUk0cIsaqBUIRAlEkmRfrEOJUYlhehtLE4pQUTGcwgkQjIRnM1nhABCnOC4RsvOJqAFCyWwsoovFkr+ygAzEqmSzQGywgBhTXcnWEvUCs4XY2m1rmxTKAAscoVyCAA)

## アプローチ3: 基数風の定義
- 0 := []
- 1 := [1]
- 2 := [1, 2]
- 3 := [1, 2, 3]

上記のように、「数」を集合の濃度として定義しようとしました。定義としては最も直感的かもしれません。

しかし、`Increment<T>`を定義しようとしたところ、エラーが出てうまくいきませんでした。`...T`は`T`が`array`型である時にしか使えないようですが、ConditionalTypeの中で`T`が`array`であることを示す方法がわかりませんでした。

```ts
// A rest element type must be an array type.
type Increment<T extends any[]> = T extends Array<infer U> ? [U, ...T] : never;
```

結果。
一応エラーは出るのですが「数」の定義がうまくいっていないので、これは納得できません。

```ts
type One    = [number];
type Two    = [number, number];
type Three  = [number, number, number];
type Four   = [number, number, number, number];

const three: Three = [1,2,3];

const valA: Two   = three; // Error
const valB: Three = three;
const valC: Four  = three; // Error
```

## まとめ
ここまでやってみたのですが、やはり「数」だけでなく、数と数との「演算」が定義されていないと面白くないですね。もっとTypeScriptと抽象代数学の知識が必要です。

### 参考
- [ConditionalTypes I/O \- TypeScript3\.4 型の強化書 \-（電子版） \- takepepe \- BOOTH](https://booth.pm/ja/items/1317204)
- [たのしいTypeScript \- Qiita](https://qiita.com/suzuki_sh/items/56cd103b713de9bae77c)
- [群・環・体 \- 大人になってからの再学習](http://zellij.hatenablog.com/entry/20121211/p1)
- [無限への誘い \- 順序型と順序数](https://ncode.syosetu.com/n4966ct/4/)
- [順序数 \- Wikipedia](https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E6%95%B0)