type-challenges をやってみる(medium編その5)

Typescript の練習として type-challenges をやった備忘録です。

前回に引き続いてやっていきます。残り 14 問、なんとかこれで解き終えて最終回にしたいです。

LastIndexOf

Implement the type version of Array.lastIndexOf, LastIndexOf<T, U> takes an Array T, any U and returns the index of the last U in Array T

問題

解答例

// type-challengesにコピペするときはコメントアウトしてください
type Equal<X, Y> =
  (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
    ? true
    : false;

type LastIndexOf<
  T extends any[],
  U,
  S extends any[] = [],
  V extends number = -1,
> = T extends [infer L, ...infer R]
  ? Equal<L, U> extends true
    ? LastIndexOf<R, U, [...S, L], S["length"]>
    : LastIndexOf<R, U, [...S, L], V>
  : V;

前回やったIndexOfと同じで実質的にEqualを作る問題ですが、 Equalについて僕は全く理解できていないので解説は下記の素晴らしい記事にお願いしたいと思います。

Unique

Implement the type version of Lodash.uniq, Unique takes an Array T, returns the Array T without repeated values.

問題

解答例

// type-challengesにコピペするときはコメントアウトしてください
type Equal<X, Y> =
  (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
    ? true
    : false;

type Includes<T extends readonly any[], U> = T extends [infer R, ...infer S]
  ? Equal<R, U> extends true
    ? true
    : Includes<S, U>
  : false;

type Unique<T extends any[], V extends any[] = []> = T extends [
  infer L,
  ...infer R,
]
  ? Includes<V, L> extends true
    ? Unique<R, [...V]>
    : Unique<R, [...V, L]>
  : V;

ひとまずいつものように再帰用のVを追加して最後には V を返すようにしておきます。

type Unique<T extends any[], V extends any[] = []> = T extends [
  infer L,
  ...infer R,
]
  ? 1
  : V;

ここで easy 編で作成した型Includes を思い出します。これを使うことでVにLが含まれていなければLをVに追加。そうでなければ追加しないというループを簡単に作る事ができました。

type Includes<T extends readonly any[], U> = T extends [infer R, ...infer S]
  ? Equal<R, U> extends true
    ? true
    : Includes<S, U>
  : false;

type Unique<T extends any[], V extends any[] = []> = T extends [
  infer L,
  ...infer R,
]
  ? Includes<V, L> extends true
    ? Unique<R, [...V]>
    : Unique<R, [...V, L]>
  : V;

MapTypes

Implement MapTypes<T, R> which will transform types in object T to different types defined by type R which has the following structure

問題

解答例

type MapTypes<T, R extends { mapFrom: any; mapTo: any }> = {
  [P in keyof T]: T[P] extends R["mapFrom"]
    ? R extends { mapFrom: T[P]; mapTo: infer To }
      ? To
      : never
    : T[P];
};

沼にはまってしまい解くのに 30 分ほどかかってしまいました 😓。無心で型をいじっていたら完成したためにうまく説明できないので正しく理解してから説明を追記します。

Construct Tuple

Construct a tuple with a given length.

問題

解答例

type ConstructTuple<
  L extends number,
  V extends unknown[] = [],
> = V["length"] extends L ? V : ConstructTuple<L, [...V, unknown]>;

いつものように再帰用の引数を追加してV["length"]がLになるまで回します。ありがたいことにLが 1000 を超えることはないので上限に引っかかりません。

Number Range

Sometimes we want to limit the range of numbers…

問題

解答例

type ConstructTuple<
  L extends number,
  V extends unknown[] = [],
> = V["length"] extends L ? V : ConstructTuple<L, [...V, unknown]>;

type NumberRange<
  L extends number,
  H extends number,
  V extends unknown[] = ConstructTuple<L>,
  U = never,
> = V["length"] extends H
  ? U | H
  : NumberRange<L, H, [...V, unknown], U | V["length"]>;

再帰用の引数を作りますが初期値に上で作成したConstructTupleを使います。このようにすればV["length"]をLから始められるので、残りはループしてあげるだけです。

Combination

It’s also useful for the prop types like video controlsList

問題

解答例

type Combination<
  T extends string[],
  U extends string = T[number],
  S extends string = U,
> = U extends string ? `${S}` | `${U} ${Combination<[], Exclude<S, U>>}` : "";

以前にPermutation をやったときには思いつきませんでしたが、ユニオン型とExcludeを使えば簡単に作れることに気づきました。自分の TypeScript 筋 💪 の成長を感じます。

Subsequence

Given an array of unique elements, return all possible subsequences.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

問題

解答例

type Subsequence<T extends unknown[]> = T extends [infer L, ...infer R]
  ? [L] | [...Subsequence<R>] | [L, ...Subsequence<R>]
  : [];

ひとまず順番が重要そうなのでinferでTを分けておきます。

type Subsequence<T extends unknown[]> = T extends [infer L, ...infer R]
  ? [L]
  : [];

type A = Subsequence<[1, 2]>;
// type A = [1]

当然これでは[1]だけになってしまうので、Rを使って再帰させることを考えます。現在の処理であればSubsequenceは常にタプルを返すのでこれを展開、[L]とのユニオン型にすれば最終的にすべての[L]になりそうです。

type Subsequence<T extends unknown[]> = T extends [infer L, ...infer R]
  ? [L] | [...Subsequence<R>]
  : [];
// type A = [] | [2] | [1]
// [1] | [...Subsequence<[2]>] ->
// [1] | [...([2] | [...Subsequence<[]> ])] ->
// [1] | [...([2] | [...[] ])] ->
// [1] | [...([2] | []) ] ->
// [1] | [2] | []

type A = Subsequence<[1, 2]>;

// タプルのユニオン型を展開したときの動作参考
// ユニオン型が取り出されるような動作
type B = [...([1] | [2, 3] | [])];
// type B = [] | [1] | [2, 3]

最後に順番を維持する必要があるので[L, ...Subsequence<R>]という風にLを先頭につけると…

type Subsequence<T extends unknown[]> = T extends [infer L, ...infer R]
  ? [L] | [...Subsequence<R>] | [L, ...Subsequence<R>]
  : [];
// [1] | [...Subsequence<[2]>] | [1, ...Subsequence<[2]>] ->
// [1] | [2] | [] | [1, ...([2] | [...Subsequence<[]>] | [2, ...Subsequence<[]> ] )] ->
// [1] | [2] | [] | [1, ...([2] | [...[]] | [2, ...[] ])] ->
// [1] | [2] | [] | [1, ...([2] | [] | [2] )] ->
// [1] | [2] | [] | [1, ...([2] | [2] )] ->
// [1] | [2] | [] | [1, 2] ->

type A = Subsequence<[1, 2]>;
// type A = [] | [1, 2] | [2] | [1]

上のような処理を経て[1, 2]に展開されます。Subsequence<[1, 2, 3]>の場合はあまりにも長いので割愛しますが、同じように[1,2,3]になります。

FirstUniqueCharIndex

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1. (Inspired by leetcode 387)

問題

解答例

type FirstUniqueCharIndex<
  T extends string,
  S extends string[] = [],
> = T extends `${infer L}${infer R}`
  ? L extends S[number]
    ? FirstUniqueCharIndex<R, [...S, L]>
    : R extends `${string}${L}${string}`
      ? FirstUniqueCharIndex<R, [...S, L]>
      : S["length"]
  : -1;

ひとまずいつものように再帰用のタプルと infer を使ってTの先頭 1 文字を取り出します。

type FirstUniqueCharIndex<
  T extends string,
  S extends string[] = [],
> = T extends `${infer L}${infer R}` ? 1 : -1;

ここで問題の繰り返されない文字について考えるとLがRの中に含まれていなければ繰り返されていないと言えそうです。つまり、

type FirstUniqueCharIndex<
  T extends string,
  S extends string[] = [],
> = T extends `${infer L}${infer R}`
  ? R extends `${string}${L}${string}`
    ? 1 // Lが繰り返しの場合の処理
    : 2 // Lが繰り返しでない場合の処理
  : -1;

${string}${L}${string}については、Template Literal Types を参照してください。残りはSに現在の Index を保持させるようにして再帰させてみます。

type FirstUniqueCharIndex<
  T extends string,
  S extends string[] = [],
> = T extends `${infer L}${infer R}`
  ? R extends `${string}${L}${string}`
    ? FirstUniqueCharIndex<R, [...S, L]>
    : S["length"]
  : -1;

type A = FirstUniqueCharIndex<"aabb">;
// type A = 1

エラーがでてしまっており問題があるようです。冷静に処理を追うと 2 回目の再帰の際Tには"abc"が入るので、Lが"a",Rが"bb"と推測されます。当然"a"は"bb"には含まれないのでこの時点でのS["length"]===1が返ってしまいます。

これを避けるために、SにLが含まれているかどうかの判定を追加し、含まれていればすぐに再帰するように変更することで上の問題を解決します。

type FirstUniqueCharIndex<
  T extends string,
  S extends string[] = [],
> = T extends `${infer L}${infer R}`
  ? L extends S[number] // ここでSにLが含まれているか判定
    ? FirstUniqueCharIndex<R, [...S, L]>
    : R extends `${string}${L}${string}`
      ? FirstUniqueCharIndex<R, [...S, L]>
      : S["length"]
  : -1;

GetMiddleElement

Get the middle element of the array by implementing a GetMiddleElement method, represented by an array

If the length of the array is odd, return the middle element If the length of the array is even, return the middle two elements

問題

解答例

type GetMiddleElement<T extends unknown[]> = T["length"] extends 2
  ? T
  : T extends [infer _L, ...infer C, infer _R]
    ? GetMiddleElement<C>
    : T;

とりあえず infer と再帰を使ってTの両端の要素を 1 つずつ取り除きます。1 つずつ取り除いていけば最終的にはTの要素数は 1 か 2 になるだろうという思考です。

type GetMiddleElement<T extends unknown[]> = T extends [
  infer _L,
  ...infer C,
  infer _R,
]
  ? C
  : T;

type A = GetMiddleElement<[1, 2, 3, 4, 5]>;
// type A = [3]
type B = GetMiddleElement<[1, 2, 3, 4, 5, 6]>;
// type B = []

Tの要素数が偶数の時、最終的にCが[ ]と推測されてしまい思ったような動作をしないので、再帰させる前にTの要素数が 2 の際は特例として再帰させずにTを返すようにします。

type GetMiddleElement<T extends unknown[]> = T["length"] extends 2
  ? T
  : T extends [infer _L, ...infer C, infer _R]
    ? GetMiddleElement<C>
    : T;

type A = GetMiddleElement<[1, 2, 3, 4, 5]>;
// type A = [3]
type B = GetMiddleElement<[1, 2, 3, 4, 5, 6]>;
// type B = [3, 4]

Integer

Please complete type Integer<T>, type T inherits from number, if T is an integer return it, otherwise return never.

問題

解答例

type Integer<T> = T extends number
  ? `${T}` extends `${number}.${number}`
    ? never
    : number extends T
      ? never
      : T
  : never;

T extends numberを付けないようにしていたためにあまり美しくない感じになってしまいました。

やっている事自体は単純なので解説は割愛しますが、重要なのはnumber extends TでTがnumberだったときの分岐をすることだと感じました。

ToPrimitive

Convert a property of type literal (label type) to a primitive type.

問題

解答例

type Convert<
  T,
  P extends any[] = [string, number, boolean, unknown],
> = P extends [infer L, ...infer R] ? (T extends L ? L : Convert<T, R>) : never;

type ToPrimitive<T> = {
  [P in keyof T]: T[P] extends Record<any, any>
    ? ToPrimitive<T[P]>
    : Convert<T[P]>;
};

いきなり「オブジェクト型を展開してなんやかんやして…」と考えるとしんどいので、TをプリミティブにするようなConvert<T>を考えます。

何も考えずextendsを大量に使ってもいいのですが、流石に辛いので再帰で回すようにします。

Everyday Types(プリミティブがたくさん書いてあります)

type Convert<
  T,
  P extends any[] = [string, number, boolean, unknown],
> = P extends [infer L, ...infer R] ? (T extends L ? L : Convert<T, R>) : never;

type A = Convert<"aaaa">;
// type A = string
type B = Convert<123>;
// type B = number
type C = Convert<true>;
// type C = boolean
type D = Convert<() => any>;
// type D = unknown

こうしておけば仮にプリミティブな型が増えてもPに増やすだけでよくなります。 nullやundefined等は今回の例にないのでPに入れてませんが増やせば問題ありません。

残りはこれをToPrimitive<T>のTに使うだけです。最終的に下のようになりました。

type Convert<
  T,
  P extends any[] = [string, number, boolean, unknown],
> = P extends [infer L, ...infer R] ? (T extends L ? L : Convert<T, R>) : never;

type ToPrimitive<T> = {
  [P in keyof T]: T[P] extends Record<any, any>
    ? ToPrimitive<T[P]>
    : Convert<T[P]>;
};

DeepMutable

Implement a generic DeepMutable which make every parameter of an object - and its sub-objects recursively - mutable.

問題

解答例

type DeepMutable<T extends Record<any, any>> = {
  -readonly [P in keyof T]: T[P] extends (...args: any) => any
    ? T[P]
    : T[P] extends Record<any, any>
      ? DeepMutable<T[P]>
      : T[P];
};

上と同じように再帰しながらreadonlyを外していきます。ただし() => 1はRecord<any,any>に割り当て可能なので先に関数の判定をする必要があり、そこでしばらく沼ってました。

All

Returns true if all elements of the list are equal to the second parameter passed in, false if there are any mismatches.

問題

解答例

// type-challengesにコピペするときはコメントアウトしてください
type Equal<X, Y> =
  (<T>() => T extends X ? 1 : 2) extends <T>() => T extends Y ? 1 : 2
    ? true
    : false;

type All<T extends any[], A extends any> = T extends [infer L, ...infer R]
  ? Equal<L, A> extends true
    ? All<R, A>
    : false
  : true;

T[number]でユニオン型を作りそれがAに割り当て可能かチェックします。

今回のテストケースだと下のような型でもエラーはでないのですが、[1, 1, 1, never]のような型が与えられた際に予想と異なる動作をするので、Equalを使って厳密に判定しています。

type All<T extends any[], A extends any> = T[number] extends A ? true : false;

type A = All<[1, 1, 1, never], 1>;
// type A = true

Filter

Implement the type Filter<T, Predicate> takes an Array T, primitive type or union primitive type Predicate and returns an Array include the elements of Predicate.

問題

解答例

type Filter<T extends any[], P extends any, V extends any[] = []> = T extends [
  infer L,
  ...infer R,
]
  ? L extends P
    ? Filter<R, P, [...V, L]>
    : Filter<R, P, V>
  : V;

いつも通り再帰用のVを追加し、1 文字取り出してPに割り当て可能か判定、可能ならVにLを追加して再帰をしています。

終わりに

これでついに medium 編完了です!!👏

色々調べてとても勉強になり、型パズル力を解く前に比べて圧倒的に強くすることができました。ですがまだ良くわかっていないところ、例えばEqualの動作について理解できていないので、記事を作るという名目でいつか詳しく調べたいと思います。

hard 編はこれから違う勉強をする予定なので、すぐにやることはないと思いますがどこかで解きたいなと思っています。

今回はこれで終わりです。駄文を読んでくださりありがとうございました。