TypeScriptの型レベル連結リスト活用術：型を変えられるコンテナを作る

皆さんこんにちは。この記事では、TypeScriptにおいて**型レベル連結リスト**が役に立つ一例をご紹介します。当初以下のように練習問題の形でツイートしたところ、[型レベル連結リストを用いる想定解にたどり着いた方がいました](https://twitter.com/kgtkr/status/1223524412458094592)。おめでとうございます。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">TypeScript練習問題：　このようなContainer型をつくれ（ぇ <a href="https://t.co/zq25GiXDM2">https://t.co/zq25GiXDM2</a> <a href="https://t.co/llveS6MCjG">pic.twitter.com/llveS6MCjG</a></p>&mdash; 🈚️うひょ🤪✒📘 (@uhyo_) <a href="https://twitter.com/uhyo_/status/1223492212350181377?ref_src=twsrc%5Etfw">February 1, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

## 型レベル連結リストとは

連結リストはリストの表現方法の一種です。連結リストではリストの各要素が「自身の値」と「次の要素への参照」（あるいは次の要素そのもの）を保持しています。リストの各要素には、先頭要素から順番にたどることでアクセスできます。

型レベル連結リストでは、連結リストの構造を型として表現します。型レベルということで、型レベル連結リストの要素は型です。例えば`number`, `string`, `number`の3要素からなる型レベル連結リストは、TypeScriptで次のように表現できます。

```ts
type L = {
  value: number;
  next: {
    value: string;
    next: {
      value: number;
    }
  }
};
```

一つのオブジェクト型が連結リストの1要素です。要素は`value`プロパティで自身の要素を保持し、また`next`プロパティで次の要素を保持します。最後の要素は`next`プロパティを持ちません。

この表現だと0要素の連結リストを表現する方法がありませんが、今回は特に問題ではありません。

## 型レベル連結リストの利点

型レベル連結リストをこのように表現した場合、大きな利点が一つあります。それは、**前方一致関係と部分型関係が一致する**ということです。具体的に言えば、型レベル連結リスト`S`と`T`について、`S`が`T`のprefixである（`T`の最初のいくつかの要素を取り出すと`S`になる）ならば、`T`は`S`の部分型となります。

具体例を見てみましょう。次の例では`S`は`number`, `string`からなる2要素のリストであり、`T`は`number`, `string`, `number`からなる3要素のリストあり、`S`は`T`に前方一致しています。コード中で確かめられているように、`T`は`S`の部分型となっています。

```ts
type S = {
  value: number;
  next: {
    value: string;
  }
};
type T = {
  value: number;
  next: {
    value: string;
    next: {
      value: number;
    }
  }
};

// TがSの部分型であることを確かめる
declare const t: T;
const s: S = t;
```

ちなみに、タプル型を用いて型レベルリストを`[number, string]`とか`[number, string, number]`のように表現した場合はこの性質が成り立ちません。これら2つの型は非互換な`length`プロパティを持つからです（前者の`length`プロパティは`2`型を持ち、後者は`3`型を持ちます）。

型レベルリストが欲しい場合ほとんどの場合はタプル型を用いた方法で十分ですが、「前方一致関係と部分型関係が一致する」という性質が必要な場合は今回紹介した型レベル連結リストの手法が役に立ちます。

そして、ここからはこの性質が実際に活きる場合を紹介します。それが、冒頭のツイートで述べた「練習問題」です。

## 練習問題：型を変えられるコンテナを作る

今回の問題は、次のような挙動をする`container`を作るというものです。

```ts
const container: Container<{ value: number }> = makeContainer(123);

const num: number = container.data;

container.setData("foobar");

const str: string = container.data;

container.setData(true);

const bool: boolean = container.data;
const notNum: number = container.data;
const notStr: string = container.data;
```

この例では、最初`container.data`は`number`型です。しかし、`container.setData`を呼び出して文字列を渡すと、`container.data`は`string`型に変わります。さらに`container.setData`に真偽値を渡すと`container.data`は`boolean`型に変わります。

このように、`container`は`setData`を呼び出すとそれに応じて`container.data`の型が変わってしまいます。このような特性を持つ`container`を実装するというのが今回の課題です。

### 素朴な解法とその問題点

今回`container.data`の型が変わっているということは、`container`の型が変わっているということです。しかし、TypeScriptでは変数の型は宣言時に決まるのが原則であり、（条件分岐で型が絞り込まれる場合を除いて）変数の型が後から変わることは基本的にはありません。

しかし、その原則を破って変数の型を後から変える方法が一つあります。筆者の記事を読んでくださっている熱心な方ならば、以下の記事で紹介した`asserts`を使えばいいことはすぐに分かるでしょう。

- [TypeScript 3.7のasserts x is T型はどのように危険なのか](https://qiita.com/uhyo/items/b8d2ea6fbf6214fc4194)

TypeScript 3.7で導入された`asserts`構文を用いれば、メソッド呼び出しに伴って変数の型を変えることができます。特に、この記事の最後で説明した`asserts this is`パターンを用います。これを使って素朴に実装しようとすると、以下のようになるでしょう。

```ts
class Container<T> {
    data: T;
    constructor(data: T) {
        this.data = data;
    }
    setData<U>(newData: U): asserts this is Container<U> {
        (this as any).data = newData;
    }
}
const makeContainer = <T>(data: T) => new Container(data);
```

`Container<T>`は、`data`が`T`型のコンテナの型です。`setData`の型宣言では返り値を`asserts this is Container<U>`としています。これは「`container.setData`を`U`型の値で呼び出すと`container`の型が`Container<U>`型になる」という意味です。

一見これで良さそうに見えますが、実はこれでは問題があります。これを実際に使ってみると思った結果にはなりません。

```ts
const container: Container<number> = makeContainer(123);

const num: number = container.data; // container.data は number型

container.setData("foobar");

const str: string = container.data; // container.data は never型
```

`container.setData("foobar")`のあと、`container.data`は`string`型になってほしいところですが、実際には`never`型となってしまいます。

その理由は`setData`呼び出しのあとの`container`の型を見てみればわかります。`container`の型は`Container<string>`となっていて欲しいところ、実際には`Container<number> & Container<string>`型となっています。つまり、`asserts this is`は型を完全に書き換えるのではなく、元の型とのintersection型が取られるのです。これには、`asserts`が行うのはあくまで型の絞り込みであるという考え方が見て取れます。

`container`が`Container<number> & Container<string>`型だと、`container.data`が`number & string`型になってしまいます。数値かつ文字列であるような値は存在しませんから、これは`never`型に解決されます。

ということで、`Container<T>`を正しく実装するためには、この`asserts`の制限に耐える実装としなければいけないことが分かりました。

### 解決編(1) 型レベル連結リストによる解決

今回問題だったのは、`Container<U> & Container<T>`という型が発生すると中身の型が`U & T`となってしまうことでした。例えば`string`と`number`が混ざると`never`となってしまいます。この問題を回避するためには、`&`で合成されても情報が混ざらないような表現方法を考えれば良いですね。そのために型レベル連結リストを用いることができます。

初期状態を`{ value: number }`として中身が`number`型であることを表し、`setData("foobar")`のあとは`{ value: number; next: { value: string } }`として「最初`number`型で次に`string`型になった」ことを表します。

こうすることで、両者が`&`で混ぜられたとしても`{ value: number } & { value: number; next: { value: string } }`は`{ value: number; next: { value: string } }`ですから、`number`と`string`が混ざらずに情報が保持されています。ここで記事の最初で紹介した型レベル連結リストの性質が活きています[^note_1]。

[^note_1]: 実際のところ、異なる階層にデータを保存していれば混ざらないので型レベル連結リストが唯一の方法という訳でもありません。ここでは汎用性のあるデータ構造として型レベル連結リストを推奨しています。

ということで、実際のコードを見てみます。まず2つの補助型関数を定義します。

```ts
type Append<List, T> = List extends { value: infer V; next: infer N }
    ? { value: V; next: Append<N, T> }
    : List extends { value: infer V }
    ? { value: V; next: { value: T } }
    : never
type Last<List> = {
    n: List extends { next: infer N } ? Last<N> : never;
    v: List extends { value: infer V } ? V : unknown;
}[List extends { next: any } ? "n" : "v"];
```

`Append<List, T>`と`Last<List>`が型レベル連結リストの操作を担う補助型関数です。`Append<List, T>`はリスト`List`の最後に`T`を追加した新しいリストを返します。例えば`Append<{ value: number }, string>`は`{ value: number; next: { value: string } }`となります。最後に追加するという操作なので$O(N)$となりますが、仕方ありません。

また、`Last<List>`は与えられたリストの最後の要素を返します。例えば`Last<{ value: number; next: { value: string } }>`は`string`です。こちらも$O(N)$ですね。

これらを用いて、実際の`Container<Data>`の定義は以下のようになります。先の例では`Data`はデータの実際の型でしたが、今回は代わりに前述の型レベルリストがここに入ります。よって、初期状態で`number`が入っているコンテナの型は`Container<{ value: numbner }>`となります。

```ts
class Container<Data> {
    public data: Last<Data>;
    constructor(data: any) {
        this.data = data;
    }
    public setData<T>(value: T): asserts this is Container<Append<Data, T>> {
        (this as any).data = value;
    }
}
const makeContainer = <T>(data: T) => new Container<{ value: T }>(data)
```

コードを見るとわかるように、コンテナの実際の`data`プロパティの型は`Last<Data>`となります。また、`setData`の返り値は`asserts this is Container<Append<Data, T>>`となっています。つまり、現在の連結リストに新しく与えられた型を加えて新しい連結リストとしています。

次のコードでこれの動作を確認してみます。最初は`Data`は`{ value: number }`という1要素のリストですが、`container.setData("foobar")`のあとは`container`の型は`Container<{ value: number; { next: { value: string } } }>`となっています。これにより`container.data`の型が`string`となります。

```ts
const container: Container<{ value: number }> = makeContainer(123);

const num: number = container.data;

container.setData("foobar");

const str: string = container.data;

container.setData(true);

const bool: boolean = container.data;
```

同様に、さらに`container.setData(true)`とすると、`container`の型が`Container<{ value: number; { next: { value: string; next: { value: boolean } } } }>`となります。これで無事に`container.data`が`boolean`型になりました。

これにて一件落着……と言いたいところですが、ひとつ不可解な点があります。最初の話では、`asserts`によって型を変えた場合は元の型とのインターセクションが取られるという話でした。しかし、今回よく見るとそうなっていません。すなわち、`container.setData("foobar")`の呼び出しの後、`container`が本来なら`Container<{ value: number }> & Container<{ value: number; next: { value: string } }>`になるはずが、`&`の左が消えてしまっています。

これは実は、`Container<{ value: number; next: { value: string } }>`が`Container<{ value: number }>`の部分型であると判定されていることが原因です。実際には`container.data`の型が違うので部分型ではないのですが、それが無視されています。これは、次のissueで報告されているTypeScriptのバグを踏んでいると考えられます。

- https://github.com/microsoft/TypeScript/issues/25344

ということで、目的は達成しているもののTypeScriptのバグに依存しており何だか釈然としません。また、誤った部分型関係が導かれてしまうということは、`Container`の誤った使い方をされると危険なコードを書けてしまうということです。よって、この穴を塞がなければいけません。

### 解決編(2) 安全性の穴を塞ぐ

安全性の穴を塞ぐには、`Data`が違うときに`Container<Data>`が部分型関係を持たないようにしなければいけません。本来はTypeScriptがきちんと判定するべきですが、前述のバグによりTypeScriptは正しくこれを判定することができず、こちらで補助する必要があります。

簡単な方法は、次のように2つのプロパティ`_data`と`_func`を追加することです。

```ts
class Container<Data> {
    private _data!: Data;
    private _func!: (data: Data) => void;
    public data: Last<Data>;
    constructor(data: any) {
        this.data = data;
    }
    public setData<T>(value: T): asserts this is Container<Append<Data, T>> {
        (this as any).data = value;
    }
}
```

プロパティ`_data`は共変の位置に`Data`を配置し、`_func`は反変の位置に`Data`を配置します。これにより、`Data`が一致していない2つの`Container<Data>`型に対して部分型関係が発生することは無くなります。

では、改めて挙動を確かめてみましょう。

```ts
const container: Container<{ value: number }> = makeContainer(123);

const num: number = container.data;

container.setData("foobar");

const str: string = container.data;
```

`container.setData("foobar")`の後の`container`の型を確かめると、`Container<{ value: number }> & Container<{ value: number; next: { value: string } }>`となっており、`&`の左が消えなくなりました。

しかし、ここで問題が発生します。`container.data`の型を調べると`never`に戻ってしまっています。一難去ってまた一難ですね。

その理由はよくよく考えてみると分かります。`container.data`の型を求める場合、まず`container`の型を求めてその`data`プロパティの型を取ることになります。今回`container`の型はインターセクション型ですから、両方の`data`プロパティを取ってインターセクションを求めることになります。そうなると、`Container<{ value: number }>`は`data`プロパティが`number`型であり、`Container<{ value: number; next: { value: string } }>`は`data`プロパティが`string`型ですから、それらのインターセクションを取って`number & string`となり、これが`never`になります。どうやら最初の問題に戻ってきてしまったようです。

本当は、先に`{ value: number }`と`{ value: number; next: { value: string } }`のインターセクションを取ってから`data`プロパティの型を計算してほしいところです。それを可能にするのが**`this`型**です。

ということで、この問題を解決した最終形を見ましょう。

### 解決編(3) `this`のトリック

いきなりですが、次のようにすれば前述の問題を解決できます。

```ts
class Container<Data> {
    _data!: Data;
    private _func!: (d: Data) => void;
    public data: Last<this["_data"]>;
    constructor(data: any) {
        this.data = data;
    }
    public setData<T>(value: T): asserts this is Container<Append<this["_data"], T>> {
        (this as any).data = value;
    }
}
const makeContainer = <T>(data: T) => new Container<{ value: T }>(data)
```

`data`プロパティや`setData`メソッドの型において、`Data`を使っていた部分が`this["_data"]`に変わっています。`this`型経由で参照されるプロパティは`private`であってはいけないため`_data`の宣言から`private`が外れました。

なぜこれでうまく行くのかを見ます。`container.data`の型を調べるにあたってまず`container`の型が調べられるのは一緒です。`container`の型はやはり`Container<{ value: number }> & Container<{ value: number; next: { value: string } }>`です。2つの`Container`型についてそれぞれ`data`の型が取得されるのも同じです。

今回`data`の型は`Last<this["_data"]>`ですが、実はこのときの`this`の型は常に`container`の型、つまり`Container<{ value: number }> & Container<{ value: number; next: { value: string } }>`です。`&`の左側の`Container<{ value: number }>`の`data`型を計算するときであっても、`this`の型は`Container<{ value: number }> & Container<{ value: number; next: { value: string } }>`となります。

そして、`this`が`Container<{ value: number }> & Container<{ value: number; next: { value: string } }>`というインターセクション型であるとき、その`_data`の型は`{ value: number } & { value: number; next: { value: string } }`、すなわち`{ value: number; next: { value: string } }`となります。

`this`のこの特性により、`container.data`の型を計算するとき、`&`の左でも右でも`this["_data"]`の型が`{ value: number; next: { value: string } }`となることから、`data`の型は`Last<{ value: number; next: { value: string } }>`、つまり`string`型となります。これにより`container.data`の型が`string & string`、つまり`string`となります。

まとめると、`this`型の特性を用いることで`Container<{ value: number }> & Container<{ value: number; next: { value: string } }>`というインターセクション型を`{ value: number } & { value: number; next: { value: string } }`というインターセクション型に変換し、それにより目的の型を得ることができました。

なお、`_data`が`private`でなくなったことで新たな危険性が生じていることに気づいた方もいるでしょう。本質ではないのでここまでの解説では省きましたが、次のようにすれば一応回避できます。

```ts
class Container<Data> {
    _data?: Data;
    private _func!: (d: Data) => void;
    public data: Last<NonNullable<this["_data"]>>;
    constructor(data: any) {
        this.data = data;
    }
    public setData<T>(value: T): asserts this is Container<Append<NonNullable<this["_data"]>, T>> {
        (this as any).data = value;
    }
}
```

## まとめ

この記事では、型を変えられるコンテナオブジェクトという題材を通じて、TypeScriptプログラミングのいくつかのテクニックを紹介しました。ひとつは、型レベル連結リストによって型に情報を付加していくテクニックです。記事冒頭で述べた性質により、古いリストと新しいリストを`&`で結合しても情報が壊れないという点がポイントです。

また、`this`型の性質も大きなポイントです。これによって、2つの`Container`型が`&`で分離されているという問題をバイパスすることができます。よく見ると`container.data`の型の計算が`setData`した回数$N$に対して$O(N^2)$かかっているような気がしますが、まあ些細な問題ですね。

### Q&A

**Q.** 型を変えられるコンテナなんて実務で使うんですか？
**A.** さあ……