🐧

【TypeScript と友達に】Type Challenges を全問解いたのでエッセンスと推し問題を紹介してみる - 後編

2023/12/10に公開

TypeScript

型

typechallenges

tech

はじめに

自己紹介

こんにちは、@kakekakemiya と申します。

現在は東京大学大学院学際情報学府の修士 1 年で、フロントエンドエンジニアとして活動しています（25 卒の就活生です）。TypeScript × React × Next.js が主戦場ですが、Flutter でモバイルアプリを開発するときもあります。

本記事は、今回は自分の TypeScript 力の向上のために、Type Challenges を全問解いたので、Type Challenges における推し問題を紹介しながら、型パズルを解く上でのエッセンスを述べていく記事の後編となります。

前編は ↓ になりますので、まだ読んでいない方はぜひこちらから先にご覧ください！

この記事の想定読者

TypeScript の型システムに興味がある方
Type Challenges が気になっている方・解いている方
基本的な型の使い方には馴染みがあるが、generics, infer, extends, union の分配則などの高度な型の使い方には馴染みがない方
自作でユーティリティ型を書いてみたい方
TypeScript の型の読解力（特に複雑なライブラリを読む力とか）を向上させたい方

推し問題とエッセンスの紹介

前編では、初級編と中級編について紹介させていただいたので、後編では上級編と最上級編について紹介させていただきます。

上級編

上級編になってくると、いつ役に立つのか？みたいな特殊ケースに対応するような問題が増えてきますが、そんななかでも、型についての見識を深められるような問題をピックアップしていきます。

19458: SnakeCase

/*
  19458 - SnakeCase
  -------
  by Gabriel Vergnaud (@gvergnaud) #hard #template-literal #string

  ### Question

  Create a `SnakeCase<T>` generic that turns a string formatted in **camelCase** into a string formatted in **snake_case**.

  > View on GitHub: https://tsch.js.org/19458
*/

/* _____________ Your Code Here _____________ */

type SnakeCase<T> = any;

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from "@type-challenges/utils";
import { ExpectFalse, NotEqual } from "@type-challenges/utils";

type cases = [
    Expect<Equal<SnakeCase<"hello">, "hello">>,
    Expect<Equal<SnakeCase<"userName">, "user_name">>,
    Expect<Equal<SnakeCase<"getElementById">, "get_element_by_id">>,
    Expect<
        Equal<
            SnakeCase<"getElementById" | "getElementByClassNames">,
            "get_element_by_id" | "get_element_by_class_names"
        >
    >
];

与えられた camelCase にフォーマットされた文字列を、snake_case に変換する SnakeCase を実装する問題です。以下が解答例です。変数の変換はこれは実務で使い得る気がしなくもないので紹介させていただました。

解答例

type SnakeCase<T extends string> = T extends `${infer F}${infer Rest}`
    ? `${F extends Uppercase<F> ? `_` : ""}${Lowercase<F>}${SnakeCase<Rest>}`
    : "";

// ちょっと再帰が増えるが、以下のように書くこともできる
type SnakeCase<T extends string> = T extends `${infer F}${infer Rest}`
    ? F extends Uppercase<F>
        ? `_${SnakeCase<Uncapitalize<T>>}`
        : `${F}${SnakeCase<Rest>}`
    : "";

この解法自体はそんなに難しくありません。string である T を　F（先頭）と Rest（残り）に分解し、F が大文字の場合は _ をつけ、小文字に変換したものを返すというものです。これを再帰的に行うことで、文字列の先頭から順に変換していきます。

ここで注視していただきたいのは、Uppercase<F> および Lowercase<F> の部分です。TypeScript には、組み込みで、文字列を大文字・小文字に変換する型があります。それが Uppercase および Lowercase です。加えて、Capitalize と Uncapitalize という型もあります。これらは、それぞれ、文字列の先頭を大文字・小文字に変換する型です。（いずれも TypeScript 4.1 で追加されました。）

公式ドキュメントはこちらです。
ただ、これ仕様よりも実装が面白くて、
/**
 * Convert string literal type to uppercase
 */
type Uppercase<S extends string> = intrinsic;

/**
 * Convert string literal type to lowercase
 */
type Lowercase<S extends string> = intrinsic;

/**
 * Convert first character of string literal type to uppercase
 */
type Capitalize<S extends string> = intrinsic;

/**
 * Convert first character of string literal type to lowercase
 */
type Uncapitalize<S extends string> = intrinsic;
intrinsic という謎右辺になっています。なんやねんってなる方は、uhyo さんのこちらの記事をご覧ください。

ここで知っておいてほしいのは、以下です。

Essence
- TypeScript には、(全体 | 先頭) を（大文字 | 小文字）に変換する型がある

類題を解きたい方は、114: CamelCase 、1383: Camelize 、9775: Capitalize Nest Object Keys などの問題もありますので、ぜひ挑戦してみてください。

55: Union to Intersection

/*
  55 - Union to Intersection
  -------
  by Zheeeng (@zheeeng) #上級 #utils #infer

  ### 質問

  高度なユーティリティ型 `UnionToIntersection<U>` を実装してください。

  > GitHubで確認する：https://tsch.js.org/55/ja
*/

/* _____________ ここにコードを記入 _____________ */

type UnionToIntersection<U> = any;

/* _____________ テストケース _____________ */
import type { Equal, Expect } from "@type-challenges/utils";

type cases = [
    Expect<Equal<UnionToIntersection<"foo" | 42 | true>, "foo" & 42 & true>>,
    Expect<
        Equal<
            UnionToIntersection<(() => "foo") | ((i: 42) => true)>,
            (() => "foo") & ((i: 42) => true)
        >
    >
];

この問題は、与えられた union から、その交差型（intersection type）を求める UnionToIntersection を実装する問題です。以下が解答例です。これは、型への理解を深めてほしいのと、解法があまりにエレガントなので紹介させていただました。

解答例

type UnionToIntersection<U> = (U extends U ? (x: U) => any : never) extends (
    x: infer V
) => any
    ? V
    : never;

これは何をやっているのでしょうか？まず、U extends U を行うことで、union を分配しています。しかし、我々が知りたいのは全体情報をもとに作成した交差型です。

その後、（(x: U) => any として分配したやつ）extends (x: infer V) => any ? V : never としています。これについて考えてみましょう。

仮に、以下のような型 F と P を考えます。

type F = ((arg: string | number) => any) | ((arg: string | null) => any);

type P = F extends (x: infer V) => any ? V : never;

このとき、P は、 F の引数を推論しようとするので、どちらの関数の引数としても成立する string （すなわち両者の交差型）を返します。

よって、UnionToIntersection は、union を一度分配したあと、全体の引数を推論する、その交差型を返すということをしています。

より厳密には、上記の方法で交差型が取得できるのは、関数の引数の型が contravariant であるためです。

共変性について言及していない上記の説明だと、以下の Foo と Bar はどちらも交差型を返しそうですが、実際には Bar のみが交差型を返します。
type Foo<T> = T extends { a: infer U; b: infer U } ? U : never;
type T10 = Foo<{ a: string; b: string }>; // string
type T11 = Foo<{ a: string; b: number }>; // string | number

type Bar<T> = T extends { a: (x: infer U) => void; b: (x: infer U) => void }
    ? U
    : never;
type T20 = Bar<{ a: (x: string) => void; b: (x: string) => void }>; // string
type T21 = Bar<{ a: (x: string) => void; b: (x: number) => void }>; // string & number
（例は公式ドキュメントから引用）

よって、上記の UnionToIntersection のようなものを実装したい場合は、対象を contravariant な型に押し込める必要があります。

このあたりの話については、

https://www.typescriptlang.org/docs/handbook/release-notes/typescript-2-8.html#type-inference-in-conditional-types

https://typescript-jp.gitbook.io/deep-dive/type-system/type-compatibility#bariansuvariance

https://typescriptbook.jp/reference/values-types-variables/array/array-type-is-covariant
あたりを参考にするといいと思います。

Essence
- infer する際、型の Variance を意識するとよい
- スマートに交差型を作るのは意外と難しい

223: IsAny

/*
  223 - IsAny
  -------
  by Pavel Glushkov (@pashutk) #上級 #utils

  ### 質問

  `any`型の値を持っているかを検出することが便利な場合があります。これは、モジュール API で`any`型の値をエクスポート可能なサードーパーティーの TypeScript モジュールを使用する際に
  特に便利です。また、implicitAny チェックを抑制する際に`any`型について知ることは良いことです。

  そこで、型`T`を受け取るユーティリティ型`IsAny<T>`を書いてみましょう。`T`が`any`型であれば`true`を返し、そうでなければ`false`を返します。

  > GitHubで確認する：https://tsch.js.org/223/ja
*/

/* _____________ ここにコードを記入 _____________ */

type IsAny<T> = any;

/* _____________ テストケース _____________ */
import type { Equal, Expect } from "@type-challenges/utils";

type cases = [
    Expect<Equal<IsAny<any>, true>>,

    Expect<Equal<IsAny<undefined>, false>>,
    Expect<Equal<IsAny<unknown>, false>>,
    Expect<Equal<IsAny<never>, false>>,
    Expect<Equal<IsAny<string>, false>>
];

これは、与えられた型 T が any 型であるかを検出する IsAny を実装する問題です。以下が解答例です。

解答例

type IsEqual<X, Y> = (<T>() => T extends X ? 1 : 2) extends <S>() => S extends Y
    ? 1
    : 2
    ? true
    : false;
type IsAny<T> = IsEqual<T, any>;

// 以下のように書くこともできる!!!!
type IsAny<T> = 0 extends 1 & T ? true : false;

前者はそりゃできるやろという感じなので、後者について見ていきます。

0 extends 1 & T は、リテラル 0 が 1 & T として解釈可能かを判定しています。この挙動について考えていきましょう。

TypeScript における交差型は、

type A = { a: string };
type B = { b: number };

type C = A & B; // { a: string, b: number }

のように使われることが（少なくともフロントエンド開発では）多いので、2 つの型をマージするというイメージで覚えていらしゃる方も少なくないと思います。しかし、それは少し誤解を招く解釈です。

実際には、交差型は、以下のように、A と B が両方とも満たす型として解釈されます。
type C = A & B; は、「C は A と B をマージした型」なのではなく、C は「A としても B としても解釈できる型」ということです。

ではなぜこの交差型が結果的に { a: string, b: number } のように、2 つの型をマージした結果になるのでしょうか？これは、TypeScript が公称型（Nominal Typing）ではなく、構造的部分型（Structural Subtyping）を採用していることに起因します。

詳しい説明は、こちらなどが参考になりますが、ざっくり言うと、TypeScript は、型自体の継承関係には着目せず、単に型同士の見た目が等しいものとして解釈可能であれば置換可能であるとみなすものです。この柔軟性が TypeScript の強みであると同時に、型の互換性を判定する際に、思わぬ挙動を引き起こすことがあります。

以下の例がわかりやすいかもしれません。

type A = { a: string };
type B = { b: number };

type C = A & B; // { a: string, b: number } となる

const c: C = { a: "a", b: 1 };

const a: A = c; // OK c は A に割り当て可能
const b: B = c; // OK c は B にも割り当て可能

type OtherA = { a: string }; // 偶然 A と同じ形を持った型
type OtherB = { b: number }; // 偶然 B と同じ形を持った型
type OtherC = { a: string; b: number }; // 偶然 C と同じ形を持った型

const otherA: OtherA = c; // OK
const otherB: OtherB = c; // OK
const otherC: OtherC = c; // OK

このように、C は A、B はおろか、OtherA、OtherB、OtherC にも割り当て可能です。これは、C が A と B の両方を満たす型として解釈されるためです。

この性質を踏まえると、type C = A & B; とは、C は A と B の両方を満たす型 = A と B のプロパティの和集合を持った型 を意味することになるため、両者がマージされたものを意味するようになるのです。

話が膨らみすぎましたが、交差型の挙動が明確化された上で 0 extends 1 & T について考えてみましょう。
この式は、0 が 1 & T として解釈可能かを判定しています。1 & T は、1 と T の両方を満たす型として解釈されるため、以下のような挙動をとります。

// T と 1 が排反 -> never となる
type P1 = 1 & string; // never
type P2 = 1 & "1"; // never

// 1 の方が制約が強い -> 1 となる
type P3 = 1 & (1 | 2); // 1
type P4 = 1 & number; // 1
type P5 = 1 & unknown; // 1

// T の方が制約が強い!! -> T となる
type P6 = 1 & any; // any

よって、0 extends 1 & T は、T が any 以外であれば、0 extends 1 もしくは 0 extends never として解釈されるため、false となります。一方、T が any であれば、0 extends any として解釈されるため、true となります。

交差型の性質をうまく利用したエレガントな解法でしたので、ここで紹介させていただきました。

Essence
- 交差型は A & B、A と B の両方として解釈可能な型を示す
- TypeScript は構造的部分型を採用している

余談ですが、TypeScript において公称型を利用したいケースは意外とあると思いますし、文字列の Enum や private なプロパティを持つクラスなどはそもそも公称型として解釈されます。公称型をあえて扱いたい場合は、

などを参考にするといいと思います。（また、Type branding や Branded Types と調べると良いと思います。演習がしたい場合は、553: Deep object to unique とかはこの話と関連性が高いです。）

最上級編

いよいよ最終ブロック、最上級編です。最上級編は正直いつ使うねんという問題が多いですが、一応何問か紹介していきます。

741: Sort

/*
  741 - Sort
  -------
  by Sg (@suica) #extreme #infer #array

  ### Question

  In this challenge, you are required to sort natural number arrays in either ascend order or descent order.

  Ascend order examples:
  Sort<[]> // []
  Sort<[1]> // [1]
  Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]> //  [2, 4, 5, 6, 6, 6, 7, 8, 9]

  The `Sort` type should also accept a boolean type. When it is `true`, the sorted result should be in descent order. Some examples:

  Sort<[3, 2, 1], true> // [3, 2, 1]
  Sort<[3, 2, 0, 1, 0, 0, 0], true> // [3, 2, 1, 0, 0, 0, 0]

  > View on GitHub: https://tsch.js.org/741
*/

/* _____________ Your Code Here _____________ */

type Sort = any;

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from "@type-challenges/utils";

type cases = [
    Expect<Equal<Sort<[]>, []>>,
    Expect<Equal<Sort<[1]>, [1]>>,
    Expect<Equal<Sort<[2, 1]>, [1, 2]>>,
    Expect<Equal<Sort<[0, 0, 0]>, [0, 0, 0]>>,
    Expect<Equal<Sort<[1, 2, 3]>, [1, 2, 3]>>,
    Expect<Equal<Sort<[3, 2, 1]>, [1, 2, 3]>>,
    Expect<Equal<Sort<[3, 2, 1, 2]>, [1, 2, 2, 3]>>,
    Expect<Equal<Sort<[3, 2, 0, 1, 0, 0, 0]>, [0, 0, 0, 0, 1, 2, 3]>>,
    Expect<
        Equal<Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9]>, [2, 4, 5, 6, 6, 6, 7, 8, 9]>
    >,
    Expect<
        Equal<Sort<[1, 1, 2, 1, 1, 1, 1, 1, 1]>, [1, 1, 1, 1, 1, 1, 1, 1, 2]>
    >,
    Expect<Equal<Sort<[], true>, []>>,
    Expect<Equal<Sort<[1], true>, [1]>>,
    Expect<Equal<Sort<[2, 1], true>, [2, 1]>>,
    Expect<Equal<Sort<[0, 0, 0], true>, [0, 0, 0]>>,
    Expect<Equal<Sort<[1, 2, 3], true>, [3, 2, 1]>>,
    Expect<Equal<Sort<[3, 2, 1], true>, [3, 2, 1]>>,
    Expect<Equal<Sort<[3, 2, 1, 2], true>, [3, 2, 2, 1]>>,
    Expect<Equal<Sort<[3, 2, 0, 1, 0, 0, 0], true>, [3, 2, 1, 0, 0, 0, 0]>>,
    Expect<
        Equal<
            Sort<[2, 4, 7, 6, 6, 6, 5, 8, 9], true>,
            [9, 8, 7, 6, 6, 6, 5, 4, 2]
        >
    >
];

これは、配列を受け取り、型レベルでソートを行うという問題です。以下が解答例になります。

解答例

※ ただのソートなので真面目に追わなくて大丈夫です。

// 左側（A）が大きいかの真偽値を返す
namespace LeftIsLarger {
    export type Main<
        A extends number,
        B extends number,
        Counter extends never[] = []
    > = Counter["length"] extends A
        ? false
        : Counter["length"] extends B
        ? true
        : Main<A, B, [never, ...Counter]>;
    type Test = [
        Expect<Equal<Main<1, 2>, false>>,
        Expect<Equal<Main<2, 2>, false>>,
        Expect<Equal<Main<3, 1>, true>>
    ];
}
type LeftIsLarger<A extends number, B extends number> = LeftIsLarger.Main<A, B>;

// boolean を reverse して返す
namespace ReverseBoolean {
    export type Main<A extends boolean> = Exclude<boolean, A>;
    type Test = [
        Expect<Equal<Main<true>, false>>,
        Expect<Equal<Main<false>, true>>,
        Expect<Equal<Main<boolean>, never>>
    ];
}
type ReverseBoolean<A extends boolean> = ReverseBoolean.Main<A>;

// A, B を受け取り、{ small: 小さい方, large: 大きい方 } を返す
namespace MiniSort {
    type GetBool<
        A extends boolean,
        IsReverse extends boolean
    > = IsReverse extends true ? ReverseBoolean<A> : A;
    export type Main<
        A extends number,
        B extends number,
        IsReverse extends boolean = false
    > = GetBool<LeftIsLarger<A, B>, IsReverse> extends true
        ? { small: B; large: A }
        : { small: A; large: B };
    type Test = [
        Expect<Equal<Main<1, 2>, { small: 1; large: 2 }>>,
        Expect<Equal<Main<2, 2>, { small: 2; large: 2 }>>,
        Expect<Equal<Main<2, 1>, { small: 1; large: 2 }>>,

        Expect<Equal<Main<1, 2, true>, { small: 2; large: 1 }>>,
        Expect<Equal<Main<2, 2, true>, { small: 2; large: 2 }>>,
        Expect<Equal<Main<2, 1, true>, { small: 2; large: 1 }>>
    ];
}
type MiniSort<
    A extends number,
    B extends number,
    IsReverse extends boolean = false
> = MiniSort.Main<A, B, IsReverse>;

// バブルソートの基盤、一度のソートを゙行う
namespace SortOnce {
    export type Main<
        A extends number[],
        IsReverse extends boolean = false
    > = A extends [
        infer A0 extends number,
        infer A1 extends number,
        ...infer Rest extends number[]
    ]
        ? [
              MiniSort<A0, A1, IsReverse>["small"],
              ...Main<
                  [MiniSort<A0, A1, IsReverse>["large"], ...Rest],
                  IsReverse
              >
          ]
        : A;
    type Test = [
        Expect<Equal<Main<[1, 2]>, [1, 2]>>,
        Expect<Equal<Main<[1, 2], true>, [2, 1]>>,
        Expect<Equal<Main<[1, 4, 3, 2]>, [1, 3, 2, 4]>>,
        Expect<Equal<Main<[1, 4, 3, 2], true>, [4, 3, 2, 1]>>
    ];
}
type SortOnce<
    A extends number[],
    IsReverse extends boolean = false
> = SortOnce.Main<A, IsReverse>;

// バブルソートをする
namespace Sort {
    export type Main<
        A extends number[],
        IsReverse extends boolean = false,
        SortedA extends number[] = SortOnce<A, IsReverse>
    > = SortedA extends [...infer Rest extends number[], infer L]
        ? [...Main<Rest, IsReverse>, L]
        : [];
    type Test = [
        Equal<Sort<[3, 2, 1]>, [1, 2, 3]>,
        Expect<Equal<Main<[1, 2]>, [1, 2]>>,
        Expect<Equal<Main<[1, 2], true>, [2, 1]>>,
        Expect<Equal<Main<[1, 4, 3, 2]>, [1, 2, 3, 4]>>,
        Expect<Equal<Main<[1, 4, 3, 2], true>, [4, 3, 2, 1]>>,
        Expect<Equal<Main<[3, 2, 1]>, [1, 2, 3]>>
    ];
}
type Sort<A extends number[], IsReverse extends boolean = false> = Sort.Main<
    A,
    IsReverse
>;

正直詳細はただのバブルソートですし、真剣に追う必要はありません。
ここでお伝えしたいのは、複雑な型を実装する際に、namespace を使うといいかもしれないいうことです。

namespace は賛否両論あるので、ちょっと躊躇されますが、TypeChallenges を解く上で、Helper 型のユニットテストをスコープを閉じて書くのに便利だと思います。また、Helper 内にちょっとした private な型を書き、可読性を高めることもできます。

現実の開発環境だと、ファイル単位でスコープを閉じることができるので、namespace はあまり必要ないかもしれませんが、少なくとも Type Challenges では、namespace は有用になるケースがあるかと思います。

Essence
- 複雑な型を書くときは、namespace でスコープを閉じてテストを書くと良いかも？

めちゃくちゃ大きな型を書く問題に取り組みたい方は、476: Sum、517: Multiply（それぞれ、大きな桁数同士の足し算・掛け算を型で実装する問題）がありますので、ぜひ挑戦してみてください。

7561: Subtract

/*
  7561 - Subtract
  -------
  by Lo (@LoTwT) #extreme #tuple

  ### Question

  Implement the type Subtraction that is ` - ` in Javascript by using BuildTuple.

  If the minuend is less than the subtrahend, it should be `never`.

  It's a simple version.

  > View on GitHub: https://tsch.js.org/7561
*/

/* _____________ Your Code Here _____________ */

// M => minuend, S => subtrahend
type Subtract<M extends number, S extends number> = any;

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from "@type-challenges/utils";

type cases = [
    Expect<Equal<Subtract<1, 1>, 0>>,
    Expect<Equal<Subtract<2, 1>, 1>>,
    Expect<Equal<Subtract<1, 2>, never>>,
    // @ts-expect-error
    Expect<Equal<Subtract<1000, 999>, 1>>
];

最後にご紹介する問題は、Type Challenges の最終問題でもある Subtract です。これは、与えられた数値の差を求める Subtract を実装する問題です。以下が解答例です。

解答例

type CreateArr<
    N extends number,
    Ans extends never[] = []
> = Ans["length"] extends N ? Ans : CreateArr<N, [never, ...Ans]>;

type Subtract<A extends number, B extends number> = CreateArr<A> extends [
    ...CreateArr<B>,
    ...infer Rest
]
    ? Rest["length"]
    : never;

これは、数字を扱うには配列長がいいという知識と、extends を適切に使っている解法で、得られる物が多いかと思います。
特定の長さをもつ never の配列を生成する CreateArr という型を作り 2 つの数に対して CreateArr を適用します。

このとき CreateArr<A> extends [...CreateArr<B>,...infer Rest] が満たされる場合は、Rest が差分となります。Rest の長さを返すことで、A と B の差を求めることができます。

もう一点、注目していただきたいのが、テストケース内の

// @ts-expect-error
Expect<Equal<Subtract<1000, 999>, 1>>;

の部分です。これは、Error を期待しているという意味なのですが、どんなエラーが吐かれているかというと、Type instantiation is excessively deep and possibly infinite. というエラーです。

TypeScript は再帰回数の上限（40 回ちょっとくらいという記述を多く見かけましたが、バージョンによってはもっと多い（1000 とか？）との情報もありよくわからないので、ここでは濁させてください）を設けており、一部の抜け道はありますが、基本的には再帰回数の上限を超えるとエラーを吐きます。この仕様によって、型の実装方針が変わるケースもあると思うので、ぜひ覚えておいてください。

Essence
- TypeScript は再帰回数の上限を設けているので注意が必要
- ただし、一応抜け道は存在する

まとめ

いかがだったでしょうか？
Type Challenges は、TypeScript の型システムを深く理解するのに役立つと同時に、自分が必要としている型を書くことにも慣れることができると思います。

全てを解く必要はないですが、初級編だけでも解いてみると、型システムの理解が深まると思いますので、興味を持った方はぜひ挑戦してみてください。

2 つの記事に渡る長文でしたが、最後まで読んでいただきありがとうございました！！

この記事を気に入ってくださった方はぜひ「いいね」していただけるととても嬉しいです！！

Type Challenges と本記事の前編はこちらからどうぞ！↓