【初心者でもわかる】TypeScriptの型推論だけでフィボナッチ数列を計算する
TypeScript は JavaScript に静的型付けを与えるだけでなく、コンパイル時に型同士で計算を行う機構を備えています。本記事では「実行時にコードを走らせず、型推論だけでフィボナッチ数列を求める」という一風変わったテクニックを解説します。実務に役立つわけではありませんが、条件付き型や再帰的な型定義への理解が深まるでしょう。
はじめに
フィボナッチ数列は「0 と 1 を初項とし、次の項が直前 2 つの項の和になる数列」です。値レベルでは次のように表せます。
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n ≥ 2)
通常はループや再帰関数で計算しますが、TypeScript では型自体を再帰的に処理することでコンパイル時に結果を得ることができます。そのためには、型に対する条件分岐や抽象的な型推論を利用します。
TypeScript の型システムと条件付き型
TypeScript には、与えられた型に応じて別の型を返す条件付き型という構文があります。一般的な形は T extends U ? A : B であり、T が U に代入できる場合は A が、そうでなければ B が採用されます。これは三項演算子と似ていますが、値ではなく型に対して行われます。例えば、引数が string かどうかを判定する型エイリアスは次のように書けます。
// T が string のサブタイプなら true、それ以外なら false
type IsString<T> = T extends string ? true : false;
type A = IsString<"abc">; // true
type B = IsString<42>; // false
条件付き型は分配法則を持ち、ユニオン型に対して分配的に適用される点も特徴です。この機能を用いて、後述する数値演算を型レベルで表現します。
infer
条件付き型の中で登場する特別なキーワードが infer です。infer は「推論する」という意味で、T extends U ? A : B の U の内部から新しい型変数を取り出すために使います。具体的には、ある型 T の内部の型情報だけを抽出したいときに infer を使ってパターンマッチングを行います。
基本構文
infer の基本形は次のとおりです。
type Extracted<T> = T extends SomeType<infer U> ? U : DefaultType;
ここで T が SomeType<...> の形であれば、infer U により内部の型を U として抽出できます。条件が偽の場合は DefaultType が返されます。
具体例
-
配列の要素型の抽出：配列型から要素の型だけを取り出すユーティリティ型は次のように定義できます。
// 配列の要素型を抽出する type ElementType<T> = T extends (infer U)[] ? U : T; type Numbers = number[]; type NumberElement = ElementType<Numbers>; // number type NotArray = boolean; type NotArrayElement = ElementType<NotArray>; // booleanT extends (infer U)[]の条件により、もしTが配列型であれば内部の要素型Uを返し、配列でなければT自体を返します。 -
Promise の解決値を抽出：
Promiseが返す値の型を取り出すこともinferで実現できます。type Awaited<T> = T extends Promise<infer U> ? U : T; type PStr = Promise<string>; type Resolved = Awaited<PStr>; // string type NonPromise = number; type NonPromiseResult = Awaited<NonPromise>; // numberT extends Promise<infer U>の部分で、TがPromiseであれば解決値Uの型を返し、そうでなければT自体を返します。 -
関数の戻り値型を抽出：関数の戻り値の型を取り出すユーティリティも
inferで書けます。標準のReturnTypeの定義もinferを使って実装されています。type ReturnTypeInfer<T> = T extends (...args: any[]) => infer R ? R : never; type Fn = (x: number, y: number) => string; type FnReturn = ReturnTypeInfer<Fn>; // string type NotFunc = number; type NotFuncReturn = ReturnTypeInfer<NotFunc>; // never
infer のメリットは、複雑な型の一部を柔軟に抽出できることです。Zenn の記事では、infer を使うことで汎用的な型ユーティリティを構築でき、型安全性と可読性の向上に役立つと述べています。
数値を型で表現する – NumberToTuple
型レベルで数を扱うには、固定長の配列（タプル）を数値として扱うのが定番です。配列の length プロパティはリテラル型として扱われるため、['a', 'b']['length'] の型は 2 と推論されます。この性質を利用して「長さ N の配列」を数 N と見なします。
以下の記事では、次のような型 NumberToTuple を用意しています。
// N を受け取り、長さ N のタプル型を返す
type NumberToTuple<
T extends number,
U extends unknown[] = []
> = U["length"] extends T ? U : NumberToTuple<T, [...U, unknown]>;
// 使用例
type FiveTuple = NumberToTuple<5>; // [unknown, unknown, unknown, unknown, unknown]
この型は再帰的に unknown を追加しながら長さを増やし、最終的に U['length'] が目標値 T に達したら返すという仕組みです。これにより、数値リテラルをタプル型に変換できます。
加算と減算の型実装
タプルを使えば、加算や減算といった算術演算も実装できます。NumberToTuple から得られたタプルを結合したり分割したりして計算を行います。
加算：二つの数値 A と B の加算は、長さ A のタプルと長さ B のタプルを連結し、その長さを取得すれば良いというアイデアです。タプル型を連結すると長さが足し算になり、英語記事でも Add<A, B> = [...A, ...B]['length'] のような実装が紹介されています。
type Add<A extends number, B extends number> = [
...NumberToTuple<A>,
...NumberToTuple<B>
]["length"];
type Eight = Add<3, 5>; // 8
減算：A から B を引く場合は、長さ A のタプルを NumberToTuple<B> と残りに分解し、残りの長さを取ります。タプルの先頭に B の長さ分の要素があれば A extends [...B, ...infer Rest] という条件付き型で残り Rest を抽出でき、その長さが A - B です。
// A >= B のとき、A - B を求める
type Sub<A extends number, B extends number> = NumberToTuple<A> extends [
...NumberToTuple<B>,
...infer Rest
]
? Rest["length"]
: never;
// 1 減らす（前の数）
type Prev<N extends number> = Sub<N, 1>;
ここでは NumberToTuple<A> を [...NumberToTuple<B>, ...Rest] という形にパターンマッチングし、infer Rest により残りのタプルを取り出しています。残り部分の長さが A - B です。
フィボナッチ数列を型レベルで求める
フィボナッチ数列は、直前の 2 つの数の和で次の数が決まる数列です。型レベルで計算するには再帰的な型定義を用います。
ナイーブな再帰
単純に定義に従って Fib<N> = Fib<N-1> + Fib<N-2> と書くこともできますが、2 つの再帰呼び出しがあるため計算量が指数的に増え、型推論の深さ制限にすぐ引っかかります。ここでは紹介のみとし、効率的な方法を採用します。
末尾再帰による効率化
固定長タプルを使えば、末尾再帰で効率的にフィボナッチ数を求めることもできます。次の Fibonacci 型は第 0 項と第 1 項を初期値 [0, 1] としたタプル U を引数に持ち、T が U['length'] と一致するまでタプルに次のフィボナッチ数を蓄積し続けます。
// T 番目のフィボナッチ数を返す型
// U はフィボナッチ数列を格納したタプル（初期値 [0, 1]）
type Fibonacci<T extends number, U extends number[] = [0, 1]> = T extends 0
? 0
: T extends 1
? 1
: T extends U["length"]
? Add<U[Sub<U["length"], 1>], U[Sub<U["length"], 2>]> // 配列の最後の2つを足す
: Fibonacci<
T,
[
...U,
Add<U[Sub<U["length"], 1>], U[Sub<U["length"], 2>]> extends number
? Add<U[Sub<U["length"], 1>], U[Sub<U["length"], 2>]>
: never
]
>;
// 使用例
type F0 = Fibonacci<0>; // 0
type F1 = Fibonacci<1>; // 1
type F5 = Fibonacci<5>; // 5
type F10 = Fibonacci<10>; // 55
この型では U に現在までのフィボナッチ数列を保持しておき、T が U['length'] になるまで次の値を追加していきます。
注意点
TypeScript のコンパイラには再帰推論の深さ上限があります。数値が大きいと Fibonacci の再帰が深くなりすぎて一般化され、結果の型が単なる number になってしまいます。
参考文献
- さざなみ, 「【TypeScript】条件型と infer キーワードを理解する」
- Kotaro Suzuki, 「TypeScript の infer を使ってみる」
- Zenn 記事「指定した要素数を持つタプル型を生成する方法」
- aamulumi, “The Useless Type Calculator in Typescript”
Discussion