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

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

前回に引き続いてやっていきます。

medium だけでもう 4 記事目ですが、終わるのは 6 か 7 記事目になりそうです(残り 29 問)。

InorderTraversal

Implement the type version of binary tree inorder traversal.

解答例

type InorderTraversal<T extends TreeNode | null> = [T] extends [TreeNode]
  ? [...InorderTraversal<T["left"]>, T["val"], ...InorderTraversal<T["right"]>]
  : [];

はじめは下のようにFlatten っぽく書きましたが、エラーがでてしまいました。

type InorderTraversal<T extends TreeNode | null> = T extends TreeNode
  ? [...InorderTraversal<T["left"]>, T["val"], ...InorderTraversal<T["right"]>]
  : [];
// Type instantiation is excessively deep and possibly infinite.ts(2589)
// Expression produces a union type that is too complex to represent.ts(2590)

DeepL で翻訳してみると

型のインスタンス化が過度に深くなり、無限大になる可能性がある。
式は、表現が複雑すぎるユニオン型を生成します。

エラー内容から察するにTがTreeNodeとnullのユニオン型のためにTが分配されてループし続けてしまうとコンパイラが判断しているのだと思います。ですが、参考になりそうなページを見つけられなかったので実際のところは不明です。

今回はTを配列で包みユニオン型ではなくすことで、上のエラーが出なくなりました。

type InorderTraversal<T extends TreeNode | null> = [T] extends [TreeNode]
  ? [...InorderTraversal<T["left"]>, T["val"], ...InorderTraversal<T["right"]>]
  : [];

Flip

Implement the type of just-flip-object.

問題

解答例

type Flip<T extends Record<any, any>> = {
  [P in keyof T as `${T[P]}`]: P;
};

as は P を変更しないことに気をつけてください。

Fibonacci Sequence

Implement a generic Fibonacci<T> that takes a number T and returns its corresponding Fibonacci number.

The sequence starts: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

問題

解答例

type Fibonacci<
  T extends number,
  Arg1 extends any[] = [],
  Arg2 extends any[] = [any],
  Memo extends any[] = [],
> = Memo["length"] extends T
  ? Arg1["length"]
  : Fibonacci<T, Arg2, [...Arg1, ...Arg2], [...Memo, any]>;

フィボナッチ数列の定義

F_0=0 \\ F_1=1 \\ F_{n+1}=F_n+F_{n+1}

を愚直に書きました。Arg1 が $F_0$ 、Arg2 が $F_1$ 、Memo が $n$ に対応してます。

かなり雑に書いたので $n=20$ からエラーがでます。

type Fibonacci<
  T extends number,
  Arg1 extends any[] = [],
  Arg2 extends any[] = [any],
  Memo extends any[] = [],
> = Memo["length"] extends T
  ? Arg1["length"]
  : Fibonacci<T, Arg2, [...Arg1, ...Arg2], [...Memo, any]>;

type A = Fibonacci<20>; // A=6765
// Type produces a tuple type that is too large to represent.ts(2799)

AllCombinations

Implement type AllCombinations<S> that return all combinations of strings which use characters from S at most once.

問題

解答例

type Replace<
  S extends string,
  From extends string,
  To extends string,
> = From extends ""
  ? S
  : S extends `${infer L}${From}${infer R}`
    ? `${L}${To}${R}`
    : S;

type StrToUnion<T extends string, V = never> = T extends `${infer L}${infer R}`
  ? StrToUnion<R, V | L>
  : V;

type AllCombinations<
  S extends string,
  V extends string = "",
  U extends string = StrToUnion<S>,
> = S extends ""
  ? S
  : U extends never
    ? never
    : V | `${V}${U}` | AllCombinations<Replace<S, U, "">, `${V}${U}`>;

なんとなく書いていたらすごい長い型になりました。ざっくりとした処理の流れとしては、

Sを 1 文字ずつのユニオン型に変換(型引数U)
Uをneverと比較して分配
Sの中のUを削除して再帰

というような感じです。Permutation とかが結構似ていると思います。

Greater Than

In This Challenge, You should implement a type GreaterThan<T, U> like T > U

Negative numbers do not need to be considered.

問題

解答例

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

type GreaterThan<T extends number, U extends number> = T extends U
  ? false // T === U
  : N<T> extends [...never[], ...N<U>]
    ? true
    : false;

N<T>がN<U>より要素を持っているかどうかを検査して判定できました。ただし、T === Uの際の処理を加える必要があります。

T >= U === N<T> extends [...never[], ...N<U>]に気づけたので解けました。

Zip

In This Challenge, You should implement a type Zip<T, U>, T and U must be Tuple

問題

解答例

type Zip<T extends any[], U extends any[], V extends any[] = []> = [
  T,
  U,
] extends [[infer L1, ...infer R1], [infer L2, ...infer R2]]
  ? Zip<R1, R2, [...V, [L1, L2]]>
  : V;

[ T , U ]というふうにして infer でそれぞれの値を取り出しています。infer が便利ですね。

IsTuple

Implement a type IsTuple, which takes an input type T and returns whether T is tuple type.

問題

解答例

type TupleUnion<T extends readonly any[], V = never> = T extends readonly [
  infer L,
  ...infer R,
]
  ? TupleUnion<R, V | L>
  : V;

type IsTuple<T> = [T] extends [never]
  ? false
  : T extends []
    ? true
    : T extends readonly any[]
      ? [TupleUnion<T>] extends [never]
        ? false
        : true
      : false;

とりあえず書けたのですがその場しのぎ的な条件分岐が多いので、うまく書けたとはとてもじゃないですが思えません。

readonly T[]にT[]を割り当てできないことをこの問題で初めて気づきました。

Chunk

Do you know lodash? Chunk is a very useful function in it, now let’s implement it. Chunk<T, N> accepts two required type parameters, the T must be a tuple, and the N must be an integer >=1

問題

解答例

type Chunk<
  T extends any[],
  N extends number,
  Item extends any[] = [],
  V extends any[] = [],
> = T extends [infer L, ...infer R]
  ? Item["length"] extends N
    ? Chunk<R, N, [L], [...V, Item]>
    : Chunk<R, N, [...Item, L], V>
  : [Item, V] extends [[], []]
    ? []
    : [...V, Item];

chunkの動作のイメージはここを参考にして作りました。

ちょっと躓いたのは、T === [ ]のときに返り値が[ [ ] ]になってしまったことです。今回は単純にItem === [ ] && V === [ ]であることを検査して trueなら[ ]を返すようにしてます。

Fill

Fill, a common JavaScript function, now let us implement it with types. Fill<T, N, Start?, End?>, as you can see,Fill accepts four types of parameters, of which T and N are required parameters, and Start and End are optional parameters. The requirements for these parameters are: T must be a tuple, N can be any type of value, Start and End must be integers greater than or equal to 0.

問題

解答例

type Plus1<T extends number, V extends never[] = []> = V["length"] extends T
  ? [...V, never]["length"]
  : Plus1<T, [...V, never]>;

type Fill<
  T extends unknown[],
  N,
  Start extends number = 0,
  End extends number = T["length"],
  V extends any[] = [],
> = T extends [infer L, ...infer R]
  ? V["length"] extends End
    ? Fill<R, N, 0, End, [...V, L]>
    : V["length"] extends Start
      ? Fill<R, N, Plus1<Start>, End, [...V, N]>
      : Fill<R, N, Start, End, [...V, L]>
  : V;

適当に書いていたらすごい理解しにくいコードができていました。Vに最終的に返したい値が入っています。

やっていることは左から 1 つずつ取り出して、Start <= idx < Endなら置き換え、そうでないならそのまま戻すということをやっています。

だいぶ変なふうに上の処理を行っているので、ざっくりとした流れを下に書いておきます。

V["length"] === Endなら、つまりidx === EndならStartを適当に書き換えて再帰
V["length"] === Startなら、つまりidx === StartならNに置き換えて再帰。このときStart + 1することで次の再帰でもうまく判定できるようにしておきます

我ながらかなり気持ち悪い書き方です。もう少しわかりやすくかけるようになりたいです。

Trim Right

Implement TrimRight<T> which takes an exact string type and returns a new string with the whitespace ending removed.

問題

解答例

type TrimRight<S extends string> = S extends `${infer L}${" " | "\n" | "\t"}`
  ? TrimRight<L>
  : S;

TrimLeftの右側版です。ほぼ同じように書くことができます。

間違いなく上のFillのほうがこれより難しいと思います。

Without

Implement the type version of Lodash.without, Without<T, U> takes an Array T, number or array U and returns an Array without the elements of U.

問題

解答例

type Without<T extends any[], U, V extends any[] = []> = T extends [
  infer L,
  ...infer R,
]
  ? U extends any[]
    ? L extends U[number]
      ? Without<R, U, [...V]>
      : Without<R, U, [...V, L]>
    : L extends U
      ? Without<R, U, [...V]>
      : Without<R, U, [...V, L]>
  : V;

JavaScript でいうところのArray.prototype.filter() のようなものを作ります。

最終的な帰り値をVとして、処理の流れは下の通りです。

Tを先頭Lとそれ以外Rに分ける
Uが配列型かつU[number]にLを割り当て不可能ならVにLを加え、そうでないならLを加えて再帰
Uが配列型でなく、UにLを割り当て不可能ならVにLを加え、そうでないならLを加えて再帰

言語化能力が低すぎてうまく文字にできている気がしません。

Trunc

Implement the type version of Math.trunc, which takes string or number and returns the integer part of a number by removing any fractional digits.

問題

解答例

type Trunc<N extends string | number> =
  `${N}` extends `${infer Digit}.${number}` ? Digit : `${N}`;

Template Literal Types を使って N を整数部と小数部に分割します。分割できなければそのままNを返します。

IndexOf

Implement the type version of Array.indexOf, indexOf<T, U> takes an Array T, any U and returns the index of the first 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 IndexOf<T extends any[], U, V extends any[] = []> = T extends [
  infer L,
  ...infer R,
]
  ? Equal<L, U> extends true
    ? V["length"]
    : IndexOf<R, U, [...V, never]>
  : -1;

実質的にEqualを実装する問題ですが、ちょっと僕はまだ理解ができていないので参考にした記事を書くだけにします。

Join

Implement the type version of Array.join, Join<T, U> takes an Array T, string or number U and returns the Array T with U stitching up.

問題

解答例

type Join<
  T extends any[],
  U extends string | number,
  V extends string = "",
> = T extends [infer L extends string, ...infer R extends string[]]
  ? Join<R, U, V extends "" ? `${L}` : `${V}${U}${L}`>
  : V;

単純に再帰で 1 文字ずつくっつけていきます。ループの 1 回目だけUを挟まないようにしてあげてます。

終わりに

Equalがまたしてもでてきてしまいました。本当にこの仕組みを理解できていないので、1 度自分でソースコードを読んだほうがいいかもしれません。

おそらく次の記事で medium 編を終わることができると思います。よっぽど hard はやりません。