Zenn
🦌

type-challenges で使った TypeScript の tips

2022/11/27に公開1件
TypeScript
tech

はじめに

type-challenges は TypeScript の型システムでユーティリティ型を実装する問題集です。
型システム版の競技プログラミングといってもいいでしょう。

https://github.com/type-challenges/type-challenges

この記事では type-challenges を遊んで知った TypeScript の tips のうち、勉強になったり面白いと感じたものをまとめました。
type-challenges に挑戦して詰まったときに参考になれば幸いです。

注意

動作確認には、typescriptlang.org の Playground を利用しました。 TypeScript のバージョンは v4.8.4 （執筆時現在の最新バージョン）を使っています。 各セクションごとに書いているコードの Playground のリンクは添付しているので、動作も確認していただけます。

https://www.typescriptlang.org/play

この記事の内容は、 type-challenges の問題を解くときに使ったテクニックを中心に紹介します。
アプリケーション開発で使うような TypeScript の知識には言及しないことがあります。
たとえば、次のような事実は TypeScript を使った開発では大切な知識ですが、 type challenges に取り組むうえでは重要ではないです。

  • プリミティブ型の値は immutable なのに対し、オブジェクト型の値は mutable である
  • オブジェクト型の値は、プロパティの値が一致してもインスタンスが異なると同一と判定されない

表記について

この記事では、ジェネリック型や型変数に大文字から始める型名をつけます。ジェネリック型を使って生成した型には小文字から始まる型名をつけます。さらに、次の行にコメントアウトをつけて型の実態を添えています。エラーが発生する行には、その前の行に @ts-expect-error と一緒にエラーメッセージを残しています。

type NumberToString<T extends number> = `${T}`;

type a = NumberToString<10>;
// type a = "10";

// @ts-expect-error TS(2344) Type 'boolean' does not satisfy the constraint 'number'.
type b = NumberToString<true>;

Playground

ジェネリクス

type-challenges がユーティリティ型を実装する問題である以上、最もよく使う TypeScript の機能はジェネリクスだと言っても過言ではないです。

次の型 Tuple2 はジェネリクスを利用した型です。型変数 T を取っています。
型引数（a の Tuple2 にとって number、 b の Tuple2 にとって string）によって結果として作る型が変わります。

type Tuple2<X> = [X, X];

type a = Tuple2<number>;
// type a = [number, number];

type b = Tuple2<string>;
// type b = [string, string];

デフォルト型引数

関数のデフォルト引数のように、ジェネリクスにもデフォルト型引数を指定できます。
先頭からN番目の型変数にデフォルト型引数を指定した場合、N+1番目以降の全ての型変数にデフォルト型引数を指定する必要があります。

type Tuple3<X, Y = X, Z = boolean> = [X, Y, Z];

type c = Tuple3<number, string, null>;
// type c = [number, string, null];

type d = Tuple3<number, string>;
// type d = [number, string, boolean];

type e = Tuple3<number>;
// type e = [number, number, boolean];

型引数の制約

extends キーワードを型変数と併記することで、型引数に制約を与えることができます。

次の型 NameOf の型変数 T の型引数は、{ name: string } に代入可能な型でなければならないです。具体的には、型が string の name というプロパティを持つオブジェクト型でないといけないという制約があります。（構造的部分型の詳細は後述）

type NameOf<T extends { name: string }> = T["name"];

type f = NameOf<{ name: 'Alice' }>;
// type f = 'Alice'

type g = NameOf<{ name: string, age: number }>;
// type g = string;

// @ts-expect-error TS(2344) Type 'string' does not satisfy the constraint '{ name: string; }'.
type h = NameOf<string>;

型引数の制約がある場合、デフォルト型引数もその制約を満たす必要があります。

type AddressOf<T extends { address: string } = { address: '1-1, chiyoda, tokyo' }> = T["address"];

// @ts-expect-error TS(2344) Type '{ name: "Alice"; }' does not satisfy the constraint '{ age: number; }'. Property 'age' is missing in type '{ name: "Alice"; }' but required in type '{ age: number; }'.
type AgeOf<T extends { age: number } = { name: 'Alice' }> = T["age"];

Playground

Conditional Types

参考
https://www.typescriptlang.org/docs/handbook/2/conditional-types.html

ジェネリクスの次によく使う機能は Conditional Types だと思います。 type-challenges では型における条件分岐をしたいときに用いられます。

文法は JavaScript などの言語の三項演算子と似ていて、以下のようになります。

type a = AType extends BType ? TrueType : FalseType;

AType、BType、TrueType、FalseType にはそれぞれ任意の型を指定できます。
このとき型 a は次のようになります。

  • AType が BType に代入可能なとき、 TrueType
  • AType が BType に代入可能ではないとき FalseType

たとえば、 Conditional Types を使った次の型 a は boolean となります。

type a = 1 extends number ? boolean : string;
// type a = boolean;

それぞれの型に Conditional Types を入れ子にすることもできます。

type ToString<T> =
  T extends number 
  ? (
    T extends 1 ? 'one' : (T extends 2 ? 'two' : undefined)
  ) : (
    T extends true ? 'true' : undefined
  );

type b = ToString<2>;
// type d = 'two';

type c = ToString<true>;
// type c = 'true';

また、 True節（TrueType）の中では Type Narrowing が働き、 AType は BType に代入可能であると推論されます。

type Double<T extends number> = `2*${T}`;

type DoubleNumberOrNever<T extends number | string> =
  T extends number
  ? Double<T> // T は number に代入可能な型
  : never;

type d = DoubleNumberOrNever<5>;
// type d = "2*5";

type e = DoubleNumberOrNever<"hoge">;
// type e = never;

Playground

False節での Type Narrowing について

TypeScript の参考演算子と異なり注意すべき点は、 FalseType において Type Narrowing がない。ドキュメントでも、 Conditional Types によって TrueType （文中では 「true branch / true 節」となっている）では Type Narrowing がされると明記されているが FalseType について言及はされていない。

// TypeScript の型では、 Conditional Types の False節 において type narrowing の効果は得られない

type Double<T extends number> = `2*${T}`;
type Twice<T extends string> = `${T}${T}`;

type FailDoubleNumberOrString<T extends number | string> =
  T extends number
  ? Double<T> // T は number に代入可能な型
  // @ts-expect-error TS(2344)
  : Twice<T>; // T は string に代入可能な型として判定されない

// ↑ エラー文
// Type 'T' does not satisfy the constraint 'string'.
//   Type 'string | number' is not assignable to type 'string'.
//     Type 'number' is not assignable to type 'string'.(2344)

それっぽい issue が上がっている。
https://github.com/microsoft/TypeScript/issues/29188

このコメントに書いていることが理由っぽい。
T extends number ? "ok" : T の False 節の T を Exclude<T, number> としてしまうことができないと主張している。
たとえば T が 1 | 'a' だとすると、 T extends number は偽になるし T extends Exclude<T, number> も偽になる。

下の例では、 Crazy の型変数 T が boolean のとき、 T extends true は偽だが、 T extends Exclude<T, true> も偽なので不整合が起きている。

type True<T extends true> = `${T}`;
type False<T extends false> = `${T}`;

// この型定義が適切だと仮定する
type Crazy<T extends boolean> =
  T extends true
  ? True<T>
  : False<T>;

type a = Crazy<boolean>; // ???
// boolean extends true は偽だけど、 boolean は false に代入可能ではないので False<T> は不適切な型

このようなケースをさけるために、 False 節では Type Narrowing を意図的に実行していないということみたい。
False節で TypeNarrowing を効かせたい場合は、 Conditional Types をネストするとよい

type Double<T extends number> = `2*${T}`;
type Twice<T extends string> = `${T}${T}`;

type DoubleNumberOrString<T extends number | string> =
  T extends number
  ? Double<T> // T は number に代入可能な型
  : T extends string
  ? Twice<T>  // T は string に代入可能な型
  : never;

Playground

Distributive Conditional Types

参考
https://www.typescriptlang.org/docs/handbook/2/conditional-types.html#distributive-conditional-types

ジェネリクス型の型引数にユニオン型を与えると、 Conditional Types で型の「分配」がなされます。

下のコードでは、一見 Type extends any が無駄なように思えますが、 Distributive Conditional Types の効果で面白い挙動をとります。

type ToArray<Type> = Type extends any ? Type[] : never;

type a = ToArray<string | number>;
// type a = ???

ToArray の型引数がユニオン型なので、「分配」がなされて次のように実行されたのと同じ結果になります。

type a = ToArray<string> | ToArray<number>;

よって、 a の型は string[] | number[] です。

次の GetValueType は、ユニオン型の b の value プロパティとして使われている型の Distributive Conditional Types でそれぞれ計算しています。

type GetValueType<T extends { value: any }> = T extends any ? T["value"] : never;

type b = { value: boolean } | { value: string } | { value: { name: string | null } };
type c = GetValueType<b>;
// type c = string | boolean | { name: string | null };

Distributive Conditional Types の影響を受けずにユニオン型を扱いたい場合は、ユニオン型以外の型として認識されるようにする工夫が必要です。
下の例では [] で囲うことによってタプル型として認識されることで Distributive Conditional Types の影響を受けないようにしています。

type ToArrayNonDist<Type> = [Type] extends [any] ? Type[] : never;

type d = ToArrayNonDist<string | number>;
// type d = (string | number)[];

Playground

`never` と Distributive Conditional Typing の注意点

Conditional Types で never を扱おうとすると、想定していない挙動になることがあります。

type IsNever<T> =
  T extends never
  ? true
  : false;

type a = IsNever<never>;
// type a = never;

これは never がユニオン型の構成要素が無い状態として扱われてしまい、 IsNever<never> の結果として返るユニオン型の構成要素が無くなったことが原因です。

[] を使った Distributive Conditional Types の影響を無くす方法を紹介しましたが、 never を扱う際は常に同様の手続きが必要になります。

type IsNever<T> =
  [T] extends [never]
  ? true
  : false;

type a = IsNever<never>;
// type a = true;

Playground

型推論

参考
https://www.typescriptlang.org/docs/handbook/2/conditional-types.html#inferring-within-conditional-types

Conditional Types と infer キーワードを組み合わて、型の推論ができます。
以下の例では、 T extends Array<Item> が真になるような型 Item が存在したときに、 True 節 の中でその型変数を Item として扱うことができるようになっています。

type Flatten<T> = T extends Array<infer Item> ? Item : T;

type a = Flatten<string[]>;
// type a = string;

配列型だけでなく、オブジェクト型や関数型でも型の推論ができます。

type GetReturnType<T> = T extends (...args: any) => infer R ? R : never;

type b = GetReturnType<() => number>;
// type b = number;

type GetAfterThirdElements<T> = T extends [any, any, ...infer U] ? U : never;

type c = GetAfterThirdElements<[1, 2, 3, 4, 5]>;
// type c = [3, 4, 5];

type GetObjectName<T> = T extends { name: infer N } ? N : never;

type d = GetObjectName<{ name: "Pikachu" }>;
// type d = "Pikachu";

推論しながら型に制約を与える

参考
https://devblogs.microsoft.com/typescript/announcing-typescript-4-7/#extends-constraints-on-infer-type-variables

v4.7 から追加された機能で、 infer に extends を組み合わせることで推論をしながら制約を追加することができるようになりました。

以下の例では、 T が長さが1以上のタプル型で、かつ先頭の型 H が string に代入可能な場合のみ、 True 節で H を扱うことができます（もちろん、 H は string に代入可能な型として扱います）。

type GetFirstString<T> =
  T extends [infer H extends string, ...unknown[]]
  ? H
  : never;

type a = GetFirstString<["Hi!", "I'm", "Alice"]>;
// type a = "Hi!";

type b = GetFirstString<[1, 2, 3]>;
// type b = never;

Playground

Mapped Types

参考
https://www.typescriptlang.org/docs/handbook/2/mapped-types.html

リテラル型のユニオン型をキーとするオブジェクト型を定義できます。

type ComposeDataType<T extends string> = {
  [Key in T]: number;
}

type countryData = ComposeDataType<"Japan" | "USA" | "UK">;
// type countryData = { Japan: number; "USA": number; "UK": number; };

オブジェクト型を受け取って、プロパティの型を変換することもできます。その場合は keyof キーワードと組み合わせます。

type PropertyToNumber<T> = {
  [Key in keyof T]: number;
};

type a = PropertyToNumber<{ a: number; b: boolean; c: string | null }>;
// type a = { a: number; b: number; c: number; };

Mapping Modifiers

プロパティに readonly と ? という2種類の modifiers を適用できます。
それぞれプロパティを読み取り専用、オプショナルにすることを意味しています。

modifier を追加するときは +、除去するときは - を使います。
追加するときに限り、 + 記号を省略できます。 + を省略した形式で modifier は追加されることはよくありますが、除去も可能です。

type AddReadonly<T> = {
  +readonly [Key in keyof T]: T[Key];
};

type b = AddReadonly<{ x: number, y: boolean }>;
// type b = { readonly x: number; readonly y: boolean; };

type RemoveOptional<T> = {
  [Key in keyof T]-?: T[Key];
};

type c = RemoveOptional<{ 1?: number; 2?: null }>;
// type c = { 1: number; 2: null; };

Key Remapping

参考
https://www.typescriptlang.org/docs/handbook/2/mapped-types.html#key-remapping-via-as

as キーワードを使ってキーを置き換えることができます。
下の例では Key を capitalize したオブジェクトに変換しています。

type KeyCapitalize<T> = {
  [Key in keyof T as Capitalize<Key & string>]: T[Key];
};

type d = KeyCapitalize<{ cat: "tama"; dog: "pochi" }>;
// type d = { Cat: "tama"; Dog: "pochi"; };

また、キーを never に変換するとプロパティ自体を削除できます。

type RemoveNumberKey<T> = {
  [Key in keyof T as Key extends number ? never : Key]: T[Key];
}

type e = RemoveNumberKey<{ a: string, b: number; 0: boolean; 1: null }>;
// type e = { a: string, b: number; };

Playground

再帰

JavaScript などの多くの言語には、ある関数の中でその関数自身を呼び出す再帰呼び出しという機能が備わっています。

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n-1); // factorial 関数の中で factorial 関数自身を呼び出している
}

const x = factorial(4);
// x = 24;

同じように、TypeScript の型も再帰的に定義することができます。

type AllCapitalize<T extends string[]> =
  T extends [infer First extends string, ...infer Else extends string[]]
  ? [Capitalize<First>, ...AllCapital<Else>]
  : [];

type a = AllCapitalize<["cat", "dog", "hourse", "fish"]>;
// type a = ["Cat", "Dog", "Hourse", "Fish"];

末尾再帰

再帰呼び出しには再帰回数の上限があり、繰り返しが多すぎる処理は実行できません。
エラーメッセージから察するに、上限を設けているのは実装のしかたによって無限に型が定まらなくなる可能性があるからのようです。

// 長さが50のタプル
type a50 = [
  "a", "a", "a", "a", "a", "a", "a", "a", "a", "a",
  "a", "a", "a", "a", "a", "a", "a", "a", "a", "a",
  "a", "a", "a", "a", "a", "a", "a", "a", "a", "a",
  "a", "a", "a", "a", "a", "a", "a", "a", "a", "a",
  "a", "a", "a", "a", "a", "a", "a", "a", "a", "a"
];

// @ts-expect-error TS(2589) Type instantiation is excessively deep and possibly infinite.
type x = AllCapitalize<a50>;

再帰回数の上限を上げる方法に、末尾再帰があります。
AllCapitalize の実装を見てみると、再帰的に実行した AllCapital<Else> の結果を用いてさらに型の計算を行っています（[Capitalize<First>, ...AllCapital<Else>]）。
末尾再帰ではこのような再帰的な実行の後に計算を行わないことで、呼び出し元の型の計算を破棄しすることができ、メモリ使用量を減らせたり処理を高速化させられます。
TypeScript の型においても、末尾再帰のほうが再帰の上限回数を緩く設定されています（1000回）。
次の AllCapitalizeTailRec は、 AllCapitalize を末尾再帰で書き直しています。 Acc （「蓄積する」という意味の「accumulator」より）という型変数を導入し、計算済みの結果を保存できるようにすることで、末尾再帰にさせています。

type AllCapitalizeTailRec<T extends string[], Acc extends string[] = []> =
  T extends [infer First extends string, ...infer Else extends string[]]
  ? AllCapitalTailRec<Else, [...Acc, Capitalize<First>]>
  : Acc;

type b = AllCapitalizeTailRec<["cat", "dog", "hourse", "fish"]>;
// type b = ["Cat", "Dog", "Hourse", "Fish"];

type y = AllCapitalizeTailRec<a50>;
// type y = ["A", "A", ..., "A"];

type-challenges でも、末尾再帰を使わないと再帰回数の上限に引っかかるような問題はいくつか存在します。

ソースコードを読んでみた

現時点での最新のコード。長すぎて github で開けない

具体的な行数はカウントしてないけど、次のようなコードがある。
今回使った Playground では再帰回数の上限が50っぽいんだけど、最新版だと100になってる？
他に Type_instantiation_is_excessively_deep_and_possibly_infinite のエラーを返しているそれっぽいコードがなかったけど、詳細はわからない。

if (instantiationDepth === 100 || instantiationCount >= 5000000) {
    // We have reached 100 recursive type instantiations, or 5M type instantiations caused by the same statement
    // or expression. There is a very high likelyhood we're dealing with a combination of infinite generic types
    // that perpetually generate new type identities, so we stop the recursion here by yielding the error type.
    tracing?.instant(tracing.Phase.CheckTypes, "instantiateType_DepthLimit", { typeId: type.id, instantiationDepth, instantiationCount });
    error(currentNode, Diagnostics.Type_instantiation_is_excessively_deep_and_possibly_infinite);
    return errorType;
}

// 略

if (tailCount === 1000) {
    error(currentNode, Diagnostics.Type_instantiation_is_excessively_deep_and_possibly_infinite);
    result = errorType;
    break;
}

末尾再帰の上限は1000っぽい。

// 長さが1000のタプル
type a1000 = [
  ...a50, ...a50, ...a50, ...a50, ...a50, ...a50, ...a50, ...a50, ...a50, ...a50,
  ...a50, ...a50, ...a50, ...a50, ...a50, ...a50, ...a50, ...a50, ...a50, ...a50
];

// @ts-expect-error TS(2589) Type instantiation is excessively deep and possibly infinite.
type z = AllCapitalizeTailRec<a1000>;

Playground

Template Literal Types

参考

https://www.typescriptlang.org/docs/handbook/2/template-literal-types.html

JavaScript の Template Literal で文字列の一部にほかの文字列を挿入するように、文字列のリテラル型にほかのリテラル型を挿入した新たな型を生成することができます。

type world = "World";
type greeting = `Hello, ${world}!`;
// type greeting = "Hello, World!";

挿入する型がユニオン型になっている場合、 Template Literal Types によって生成される型もそれぞれのリテラル型を挿入してできるりテラル型のユニオン型になります。ユニオン型のリテラルが分配される Distributive Conditional Types の挙動に似ています。

type pokemon = "ピカチュウ" | "フシギダネ" | "ヒトカゲ" | "ゼニガメ";
type call = `${pokemon}、キミに決めた！`
// type call = "ピカチュウ、キミに決めた！" | "フシギダネ、キミに決めた！" | "ヒトカゲ、キミに決めた！" | "ゼニガメ、キミに決めた！"

Template Literal Types と型推論

Template Listeral Types で挿入する型の部分で型推論をすることができます。

type GetName<T extends string> = T extends `My name is ${infer Name}.` ? Name : never;

type a = GetName<"My name is Alice.">;
// type a = "Alice";

type b = GetName<"I am Bob">;
// type b = never;

また、型推論を複数組み合わせることもできます。
以下のように推論部を並べたとき、 First はちょうど1文字の、 Else は残り全て（空文字列でもよい）の文字列のリテラル型になります。

type SplitFirstLetter<T extends string> = T extends `${infer First}${infer Else}`
  ? [First, Else]
  : never;

type c = SplitFirstLetter<"abcd">;
// type c = ["a", "bcd"];

type d = SplitFirstLetter<"">;
// type d = never;

Playground

自然数の表現

type-challenges では、自然数の足し算や引き算を求める問題が出題されます。
TypeScript の型で自然数の表現に、タプル型を使った方法があります。

注意

このセクションにおける「自然数」は「0以上の整数」という意味で使っています。

配列型とタプル型

配列型 T[] は、型 T の配列を表現する型です。全ての要素の型が T です。
配列型のオブジェクトの要素の数は自然数になります。

type Numbers = number[];

const a: Numbers = [1, 2, 3, 4, 5];
// a.length = 5;

const b: Numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
// b.length = 10;

const c: Numbers = [];
// c.length = 3;

タプル型は特殊なケースの配列型で、長さと「何番目の要素が何の型か」が明確に定められています。
同じタプル型のオブジェクトの要素の数は常に一定な特定の自然数です。

type ThreeNumbers = [number, number, number];

const x: ThreeNumbers = [1, 2, 3];
// x.length = 3;

const y: ThreeNumbers = [3, 1, 4];
// y.length = 3;

配列型もタプル型も length プロパティを持つオブジェクト型です。配列型の length は number ですが、タプル型の length はそのタプルの要素数を表す整数のリテラル型です。これはそれぞれの型のオブジェクトの length プロパティの値が、配列型は自然数に、タプル型は特定の自然数になることに対応しています。

type Numbers = number[];
// Numbers["length"] = number;

type ThreeNumbers = [number, number, number];
// ThreeNumbers["length"] = 3;

タプルを使った自然数の表現

タプル型の length プロパティが特定の自然数になることを利用して TypeScript の型で自然数を表現できます。

下の例では、自然数を表現する型 Nat を定義しました。
number を Nat に変換するユーティリティ型 ComposeNat は、再帰を使って実装しています。 [unknown, ...Acc] は JavaScript のスプレッド構文のように、タプル型を展開して、要素の数が一つだけ多い新しいタプル型を構成しています。

type Nat = unknown[];

type ComposeNat<T extends number, Acc extends Nat = []> =
  Acc["length"] extends T ? Acc : ComposeNat<T, [unknown, ...Acc]>;

type zero = ComposeNat<0>;
// type zero = [];

type five = ComposeNat<5>;
// type five = [unknown, unknown, unknown, unknown, unknown];

type GetNumber<T extends Nat> = T["length"];

type a = GetNumber<ComposeNat<3>>;
// type a = 3;

type b = GetNumber<ComposeNat<10>>;
// type b = 10;

Nat の足し算の型 Add は、二つの Nat を連結させて新しい Nat を作っています。 GetNumber を使うと、連結後の Nat は元の number のリテラル型の和になっていることがわかります。連結後の型の要素の数が元の2つの Nat の要素の数の和になっているからです。

type Add<T extends Nat, U extends Nat> = [...T, ...U] & Nat;

type one = ComposeNat<1>;
type two = ComposeNat<2>;

type sum = GetNumber<Add<one, two>>;
// type sum = 3;

Nat の引き算 Subtract は、ある Nat から他の Nat を差し引いて結果を返しています。
（引き数のほうが大きいときは never を返すようにしています。）

type Subtract<T extends Nat, U extends Nat> =
  T extends [...U, ...infer V extends Nat] ? V : never;

type ten = ComposeNat<10>;
type eighteen = ComposeNat<18>;

type diff = GetNumber<Subtract<eighteen, ten>>;
// type diff = 8;

type diffMinus = Subtract<ten, eighteen>;
// type diffMinus = never;

Playground

最後に

type-challenges 自体とても楽しかったのでやってよかったです。知らなかった型の仕様を勉強するいい機会になりました。
ここで書かなかった tips もたくさんあります。ほかの人の回答も見れるので、参考にしながらチャレンジしてほしいです。

「type-challenges で使うようなテクニックって実務で使うことあるの？」と聞かれたことがあります。正直あんまり無さそうだと思いました。むしろ型を使った自然数の計算などは、使わないほうがいいとすら感じます。
しかしながら、 type-challenges を通して TypeScript の型についてちょっと詳しくなれたと思います。 Distributive Conditional Types など、初見殺しに感じる型の仕様にも触れることができました。もしかしたら、何かのコードを読んでいる際にここで得た知見に遭遇するかもしれないと期待しています（まだその経験はないですが）。

Discussion