LoginSignup
8
5

More than 1 year has passed since last update.

@ten986in株式会社ゆめみ

【おまけ問題付き】挑戦状で出したTypeScriptクイズの解説【#ゆめみからの挑戦状】

Last updated at Posted at 2023-03-13

はじめに

ゆめみの公式Twitterにて、型レベルTypeScriptの問題を2問出題しました。
こちらの問題の紹介と解説をします。
また、この記事ではTwitterでは出さなかったおまけ問題も出題します。興味ある方はチャレンジしてみてください！

出題にあたって、主に @Yametaro さん、@schrosis さんにご協力いただきました。ありがとうございます！

問題と解説

その１

問題

:arrow_down_small: PlayGround はこちらから

文字列を型引数として受け取り、 [ と ] で囲まれているならば true 、そうでないならば false となる型 を作る問題です。
型レベルで文字列に対する分岐ができるかがどうかがポイントとなります。

解答と解説

型レベル TypeScript では、Conditional Types を用いて分岐を扱えます。
Conditional Types は以下の構文で表現され、SomeType が OtherType の subtype であれば TrueType、 そうでなければ FalseType となります。 今回の問題を考える上では、SomeType が OtherType の一部である、ということが重要になります。

SomeType extends OtherType ? TrueType : FalseType;

さて、[ と ] で囲まれた文字列全てを表す型は、Template Literal Typesを用いて表すことができます。
Template Literal Types を使えば、ある文字列型や文字列型の union から別の文字列型を使うことができます。 今回は文字列全体を表すstringを用いて、[]で囲われた文字列全体を表す`[${string}]`を作ることができます。

以上を用いると、その１の答えは以下のようになります。

type IsBracketedString<S extends string> = S extends `[${string}]` ? true : false

その２に入る前に、inferについて紹介しておきます。
Conditional Types の OtherType の節にて infer R と記述すると、TrueType 節にて対応する型を R型として取り出すことができます。
先ほどの解答のstringの箇所を infer R extends string や infer R と置き換えれば、[]内の文字列型を以降扱うことができるようになります。
（置き換えるだけで置き換えて以降使用しないこともできるので、こちらの解答でも正解となります）

type IsBracketedString<S extends string> = S extends `[${infer R}]` ? true : false

取り出した R を用いる例としては、[]を外した文字列をそのまま返す型を記述できます。
[]を外す例はあまり実用的ではないですが、例えば getHoge を hoge に変換する処理などに応用できます。

type RemoveBracket<S extends string> = S extends `[${infer R}]` ? R : never
type A = RemoveBracket<"[hoge]"> // "hoge"
type B = RemoveBracket<"fuga"> // never

その2

問題

:arrow_down_small: PlayGround はこちらから

その１を発展させた問題です。[]で囲われた中身についても考える必要があります。

解答と解説

その１では、以下のことができました。

  • 「外側が[]なら true、そうでないなら false」と判定する
  • infer により中身の文字列も取得する

今回は、外側が[]なら中身の文字列に対しても再帰的に判定していき、最終的に余分な文字列がなくなった場合にのみ true とすればよくなります。

具体的には以下のアルゴリズムにより実装できます。

1. 型引数 S が空文字列であれば、（[]を取り外し切って余分な文字もないため） true となる
2. 型引数 S が `[${infer R}]` の形であれば、型引数 S に R を代入し、 1. に戻る　（[] を1つ外す操作）
3. 型引数 S が `[${infer R}]` の形でなければ、（余分な文字があるため） false となる

その2の解答例としては、以下のようになります。

type IsNestedBracket<S extends string> =
  S extends "" 
    ? true                     // S が空文字なら、[] を取り外し切って余分な文字がない
    : S extends `[${infer R}]` // [] で囲われているか
      ? IsNestedBracket<R>     // 囲われているなら、[] を1つ外して再帰
      : false                  // [] で囲われていなくて空文字でもない

ところでこれは個人的な Conditional Types の書き方なのですが、上記のように ? と : でインデントを1つ下げつつ、? と : はインデントを揃えることで見やすくなる気がします。ぜひ。

【おまけ】Twitterでは出さなかった問題と解説

記事限定のおまけ問題です。
この問題から思いつきましたが、難しかったので没となりました。

問題

文字列型の型引数を1つとる型IsParenthesesSequenceが次の条件を満たすよう、解答欄を埋めてください。

【条件】

  • 型引数が「整合性の取れたカッコ列」である場合に true となる
  • そうでない場合には false となる

ただし、「整合性の取れたカッコ列」とは、以下で定義されます。

  • 空文字列は「整合性の取れたカッコ列」です
  • 「整合性の取れたカッコ列」S, T を連結した S + T は「整合性の取れたカッコ列」です
  • 「整合性の取れたカッコ列」S を用いて、"[" + S + "]" で表される文字列は「整合性の取れたカッコ列」です。
  • これ以外は「整合性の取れたカッコ列」ではありません

【例】

  • 整合性の取れたカッコ列
    • [[[]][]]
    • [[[[[]]]]]
    • [][][][][[[]]]
    • 空文字列
  • 整合性の取れたカッコ列ではない
    • ][
    • [
    • [[[[]]]

:arrow_down_small: PlayGround はこちらから

問題について

直感的には、[] がいくつかネストしたり並べられているような文字列かどうかを判定する問題です。「整合性の取れたカッコ列」は、よく競プロの典型問題として知られています。

また余裕のある場合は、カッコの種類を [] １種類から [] () {} の３種類に増やしてみてください。

解答と解説

方針1: 前から文字列を見てパース

想定解です。

型レベルTypeScriptの典型テクニックとして、文字列や配列は（左から）1つずつ順番に見ていき、各ステップでは文字や値に応じて答えの構成や状態の遷移をするというものがあります。

この問題もこのテクニックが使えます。具体的には文字列を左から見ていき、各ステップで以下のことをすればよいです。

  • [ の場合
    • [ の中に１段入ったことを記録する
  • ] の場合
    • [ の中に入っているならば、[の中から１段出る
    • [ の中に入っていないならば、整合性が取れていないので false
  • その他の文字の場合
    • 整合性が取れていないので false
  • 空文字列（=文字列の終端となった）場合
    • [ で取っていた記録が空となっている（]により外に出切っている）か？
      • 空であれば、整合性が取れているので true
      • 空でなければ、整合性が取れていないので false

さて、この操作には記録用のスタックが必要になりますので、S 以外の型引数である T を記録用に用意しましょう。 T extends string = "" とすればデフォルト値を設定できます。
計算都合の型引数が外部に公開されてしまうのを嫌う場合は、export type Hoge<S extends string> = HogeInner<S> type HogeInner<S extends string, T extends string = ""> = never のように公開用の型を別途作成するのもいいでしょう。

このように今回の典型テクニックを使う場合、答えの構成や状態の遷移の記録用に、たびたび別の型引数を用います。

以上を考慮して、解答例はこのようになります。

type IsParenthesesSequence<S extends string, T extends string = ""> =
  S extends `[${infer S1}`               // 先頭が [ か？
    ? IsParenthesesSequence<S1, `[${T}`> // [ の中に入ったことを記録して次の文字へ
    : S extends `]${infer S1}`           // 先頭が ] か？
      ? T extends `[${infer T1}`         // 先頭が ] なら、 [ の中か？ （T により記録されているはず）
        ? IsParenthesesSequence<S1, T1>  // T の記録を1つ取り除きつつ次の文字へ
        : false                          // 先頭が ] なのに [ の中ではないので整合性が取れていない
      : S extends ""                     // 空文字（文字列の終端）か？
        ? T extends "" ? true : false    // 文字列の終端なら、[ の中から出切っているか確認
        : false                          // [ でも ] でもない文字

さて、カッコの種類を３種類に増やした場合を考えてみます。
必要な改変はこの2つです。

  • 分岐を [ だけでなく ( と { にも対応させる（カッコ閉じも同様）
  • 記録を取り除く際、対応するカッコであるかどうかを確認する

記録を取り除く際の確認は、T をスタックとして実装していれば特に影響はありません。

分岐については、単純に考えれば各分岐を３種類に対応すればよいですが、３種類の分岐を書くのは非常に面倒ですし、種類数が増減するたびに分岐を増減するのも面倒です。
種類数を増やす場合は、カッコのような値は型と分離して union として管理しつつ、カッコとカッコ閉じの対応は専用の型を用意するのが1番簡潔かな、と思います。

この変更を加えた解答はこのようになります。

type LParen = "[" | "{" | "("
type RParen = "]" | "}" | ")"

type MapRParenToLParen = {
  "]": "[",
  "}": "{",
  ")": "("
}

type IsParenthesesSequence<S extends string, T extends string = ""> =
  S extends `${infer L extends LParen}${infer S1}`                     // 分岐を LParen に変更
    ? IsParenthesesSequence<S1, `${L}${T}`>                            // マッチした LParen を記録
    : S extends `${infer R extends RParen}${infer S1}`                 // 分岐を RParen に変更
      ? T extends `${infer L extends MapRParenToLParen[R]}${infer T1}` // 対応する LParen を記録していたか
        ? IsParenthesesSequence<S1, T1>
        : false
      : S extends ""
        ? T extends "" ? true : false
        : false

ちなみに競プロに詳しい方は「カウンターとしてnumberを用意して、[で+1、]で-1、途中で負の値にならず最後0になればよいのでは？」と思ったかもしれませんが、型レベルTypeScriptには数値などという高度な概念はありません。悲しいね。
ふつう 数値を扱いたいときは配列長（"[length"]）を用います。 配列長を1つずつ増減させる操作と、カッコを1つずつ記録していく操作は変わらない操作なので、結局今回のような解法に落ち着くかなと思います。

方針2: 内側からカッコを外していく

非想定解ですが、非常に綺麗だったので紹介します。@schrosis さんによる解答です。

整合性の取れたカッコ列は、必ず [ と ] が隣り合った箇所が登場します。
整合性の取れたカッコ列の構成において、空文字列 S から "[" + S + "]" を作成したタイミングのこの [] に対応します。

この性質を用いれば、以下のように簡潔に記述できます。

type IsParenthesesSequence<S extends string> =
  S extends '' ? true // 空文字列になったら true
  : S extends `${infer L}[]${infer R}` ? IsParenthesesSequence<`${L}${R}`> // [] があったら取り除いて再帰
  : S extends `${infer L}{}${infer R}` ? IsParenthesesSequence<`${L}${R}`> // {} があったら取り除いて再帰
  : S extends `${infer L}()${infer R}` ? IsParenthesesSequence<`${L}${R}`> // () があったら取り除いて再帰
  : false // 不純物が残ったら false
8
5
0

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
8
5