LoginSignup
87
62

More than 3 years have passed since last update.

@uhyo

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

Last updated at Posted at 2020-02-02

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

型レベル連結リストとは

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

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

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の部分型となっています。

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を作るというものです。

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

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>型になる」という意味です。

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

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が混ざらずに情報が保持されています。ここで記事の最初で紹介した型レベル連結リストの性質が活きています1。

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

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 }>となります。

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となります。

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のバグを踏んでいると考えられます。

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

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

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

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

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>型に対して部分型関係が発生することは無くなります。

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

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のトリック

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

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でなくなったことで新たな危険性が生じていることに気づいた方もいるでしょう。本質ではないのでここまでの解説では省きましたが、次のようにすれば一応回避できます。

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. さあ……

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

87
62
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
87
62