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]>;
フィボナッチ数列の定義
を愚直に書きました。Arg1 が、Arg2 が、Memo がに対応してます。
かなり雑に書いたのでからエラーがでます。
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
を実装する問題ですが、ちょっと僕はまだ理解ができていないので参考にした記事を書くだけにします。
- https://qiita.com/Quramy/items/b45711789605ef9f96de
- https://zenn.dev/yumemi_inc/articles/ff981be751d26c
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 はやりません。