generated at
Conditional Typesを末尾再帰で書く
Conditional Typesを用いた再帰型は、末尾再帰で書くと、ネストを深くできる
TypeScript v4.5からConditional Typesが末尾再帰の最適化されるようになった
ここでの「最適化」は、ネストに対する許容と捉えるのが良い
Tail-Recursion Elimination on Conditional Types


https://github.com/microsoft/TypeScript/pull/45711


何が嬉しいか？
TypeScriptの型は再帰が深すぎると、型エラーが生じる
ここで、末尾再帰で書くようにすると、それがかなり許容される
TypeScriptの再帰制限が緩和されるということ
つまり、自分で再帰型を定義する際に、末尾再帰になるように心がければ良い



例
引数にとった文字列を、1文字ずつ要素にした配列型に変換する型を考える
末尾再帰でない書き方で書くと以下のようになる
ts
type Split<S> = S extends `${infer Char}${infer Rest}` ? [Char, ...Split<Rest>] : [];
全く同じ挙動をするものを末尾再帰で書くと以下のようになる
ts
type SplitTR<S extends string> = Split_<S, []>; type Split_<S extends string, RS extends string[]> = S extends `${infer H}${infer Tail}` ? Split_<Tail, [H, ...RS]> : RS;
補助型関数 Split_ を導入し、これが末尾再帰になっている
これら2つの型に長さ50の文字列を与える
4.5.ts
type R1 = SplitTR<'01234567890123456789012345678901234567890123456789'>; // ok type R2 = Split<'01234567890123456789012345678901234567890123456789'>; // ng
4.4.ts
type R1 = SplitTR<'01234567890123456789012345678901234567890123456789'>; // ng type R2 = Split<'01234567890123456789012345678901234567890123456789'>; // ng
v4.5では、末尾再帰にした時にのみerrorが出ない
v4.4では、いずれの場合もerrorが出る
具体的な数字にどれほど意味があるのかはわからないが、数えてみると以下の感じだった
v4.5の末尾再帰は、1000文字までok
v4.5の末尾再帰でないものは、48文字までok




結果がunionな末尾再帰は、最適化の恩恵が受けられない
これはerrorになる
ts
type GetChars<S> 　　　　　=　S extends `${infer Char}${infer Rest}` 　　　　　 ? Char | GetChars<Rest> 　　　　　 : never;
たしかに、これも一種の末尾再帰と言えるmrsekut
以下のように書き直せば良い
ts
type GetChars<S> = GetCharsHelper<S, never>; type GetCharsHelper<S, Acc> =　S extends `${infer Char}${infer Rest}` ? GetCharsHelper<Rest, Char | Acc> : Acc;


Haskellでも頻出するし、末尾再帰あるあるだと思うけど、補助関数を使えば末尾再帰は作りやすいmrsekut