tail-recursive-generics

末尾再帰型のジェネリック型を優先する

概要

TypeScript では、無限ループを防ぐために型のインスタンス化の深さが制限されています。「Type instantiation is excessively deep and possibly infinite」というエラーが発生した場合は、再帰型を末尾再帰にリファクタリングする必要があります。アキュムレータパターンを使えば、TypeScript が最適化できる型を記述でき、深さの制限を回避できます。

これは、大規模または深くネストされた構造を処理する型レベルプログラミングに不可欠です。

このスキルを使う場面

• 「Type instantiation is excessively deep」エラーが発生したとき
• 再帰的なジェネリック型を記述するとき
• 大規模な型構造を処理するとき
• 型レベルのループや反復処理を構築するとき
• 深くネストされたオブジェクト変換を行うとき

絶対的なルール

アキュムレータパターンを使って、ジェネリック型を末尾再帰にします。ネストされた型構造を組み立てるのではなく、蓄積した結果を型パラメーターとして渡します。

検出

次のような症状に注意してください。

// ERROR: Type instantiation is excessively deep
type DeepTransform<T> = T extends object
  ? { [K in keyof T]: DeepTransform<T[K]> }
  : T;

// Works for shallow objects, fails for deeply nested ones
type Test = DeepTransform<{ a: { b: { c: { d: { e: string } } } } }>;

問題：末尾再帰ではない再帰

// BAD: Non-tail-recursive - builds nested type structure
type NTuple<T, N extends number> = 
  N extends 0 
    ? []
    : [T, ...NTuple<T, Subtract<N, 1>>];
//          ^^^^^^^^^^^^^^^^^^^^^^^^^^
//          Recursive call not in tail position
//          TypeScript can't optimize this

// Each recursive call adds a layer:
// NTuple<T, 3> = [T, ...NTuple<T, 2>]
//              = [T, ...[T, ...NTuple<T, 1>]]
//              = [T, ...[T, ...[T, ...[]]]]
// Depth grows with N

解決策：アキュムレータを使った末尾再帰

// GOOD: Tail-recursive with accumulator
type NTuple<T, N extends number> = NTupleHelp<T, N, []>;

type NTupleHelp<T, N extends number, Acc extends T[]> =
  Acc['length'] extends N
    ? Acc
    : NTupleHelp<T, N, [T, ...Acc]>;
//    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
//    Recursive call is in tail position
//    TypeScript can optimize this

// Accumulator builds result iteratively:
// NTupleHelp<T, 3, []>
// → NTupleHelp<T, 3, [T]>
// → NTupleHelp<T, 3, [T, T]>  
// → NTupleHelp<T, 3, [T, T, T]>
// → [T, T, T] (Acc['length'] extends 3)

実例：ディープ読み取り専用型

// BAD: Non-tail-recursive, hits depth limit
type DeepReadonly<T> = T extends object
  ? { readonly [K in keyof T]: DeepReadonly<T[K]> }
  : T;

// GOOD: Tail-recursive with accumulator
type DeepReadonly<T> = DeepReadonlyHelp<T, []>;

type DeepReadonlyHelp<T, Seen extends unknown[]> = 
  T extends object
    ? T extends Seen[number]  // Check for circular reference
      ? T
      : { 
          readonly [K in keyof T]: DeepReadonlyHelp<
            T[K], 
            [T, ...Seen]  // Accumulate seen types
          > 
        }
    : T;

// Usage
type Deep = DeepReadonly<{
  a: { b: { c: { d: { e: { f: string } } } } }
}>;
// Works without hitting depth limit!

文字列変換の例

// BAD: Non-tail-recursive string replacement
type ReplaceAll<S extends string, From extends string, To extends string> =
  S extends `${infer Before}${From}${infer After}`
    ? `${Before}${To}${ReplaceAll<After, From, To>}`  // Not tail-recursive
    : S;

// GOOD: Tail-recursive with accumulator
type ReplaceAll<S extends string, From extends string, To extends string> =
  ReplaceAllHelp<S, From, To, ''>;

type ReplaceAllHelp<
  S extends string,
  From extends string,
  To extends string,
  Acc extends string
> = S extends `${infer Before}${From}${infer After}`
  ? ReplaceAllHelp<After, From, To, `${Acc}${Before}${To}`>
  : `${Acc}${S}`;

// Usage
type Result = ReplaceAll<'foo-bar-baz', '-', '_'>;
// 'foo_bar_baz' - works for long strings!

主な原則

// 1. Pass accumulator as type parameter
type Transform<T, Acc = []> = /* ... */;

// 2. Recursive call must be in tail position
// BAD:  [T, ...Recursive<...]  // Spread is not tail position
// GOOD: Recursive<..., [...Acc, T]>  // Accumulator updated

// 3. Base case checks accumulator
type Helper<T, Acc> = Condition<Acc> extends true
  ? Acc  // Return accumulated result
  : Helper<T, Update<Acc>>;  // Continue with updated accumulator

末尾再帰が役に立たない場合

本質的に深くなる型もあります。

// Pathological case: deeply nested object
type Deep = {
  a: { b: { c: { d: { e: { f: { g: string } } } } } }
};

// Even tail-recursive types may struggle with
// objects nested 50+ levels deep

深さ制限への対処手順

深さ制限エラーが発生した場合：

1. 再帰を特定する：問題を引き起こしている再帰型を見つけます
2. アキュムレータを追加する：アキュムレータパラメーターを持つヘルパー型を作成します
3. 末尾位置に移動する：再帰呼び出しが最後の操作になるようにします
4. 深いケースでテストする：深くネストされた型を処理できることを確認します
5. 代替策を検討する：ランタイム検証のほうが適している場合もあります

危険信号

アンチパターン	問題	解決策
タプル内の ...Recursive<...>	末尾再帰ではありません	アキュムレータを使います
アキュムレータを使わない深いネスト	深さ制限に達します	アキュムレータパラメーターを追加します
条件型内の再帰呼び出し	最適化されない可能性があります	構造を変更します

よくある正当化

「TypeScript の深さ制限を増やせばいい」

実際には：そのための設定はありません。この制限は無限ループを防ぐためのものです。

「自分の型はそこまで深くない」

実際には：生成された型（GraphQL など）は、想定より深くなることがあります。末尾再帰にすると、型が堅牢になります。

「これは複雑すぎる」

実際には：パターンはシンプルです。ヘルパー型とアキュムレータを使います。一度習得すれば、どこでも応用できます。

クイックリファレンス

パターン	末尾再帰ではない	末尾再帰
タプルの構築	[T, ...Rec<N-1>]	Rec<N, [T, ...Acc]>
文字列の構築	`${X}${Rec<Y>}`	`Rec<Y, `${Acc}${X}`>`
オブジェクトの走査	{ [K]: Rec<T[K]> }	Rec<T[K], [T, ...Acc]>

まとめ

アキュムレータパターンを使って、再帰的なジェネリック型を末尾再帰にします。これにより、「excessively deep」エラーを回避し、任意の規模の入力でも型が機能するようになります。

参考資料

• Dan Vanderkam 著『Effective TypeScript』第2版
• 項目57：末尾再帰型のジェネリック型を優先する