📑

TypeScriptの型を使ってFizzBuzzとフィボナッチ数を計算してみた

2021/02/14に公開

きっかけ

最近はTypeScriptの型の導出が面白くてtype-challengesリポジトリの問題を解いてます。
その中のLast of Arrayという問題は配列Tの最後の要素の型を返すLast<T>を実装する問題で、最初T[T['length']-1]とすれば良いと安易に考えたところ、型レベルでは数値の演算は定義されていないのでエラーなってしまいました。結局inferを使って配列とのパターンマッチで解決できたのですが、この問題の解決のために型での数値演算を考えたのでその発展としてFizzBuzzとフィボナッチ数の計算をしてみました。

数値演算

準備

type-challengesを進めていく中で固定長配列型のlengthで数値リテラルが取得できることを知ったので、配列のlengthを利用して計算を定義する。
まず数値を指定するとその長さの配列の型を返す型を定義する

type NumberToTuple<T extends number, U extends unknown[] = []> = U['length'] extends T ? U : NumberToTuple<T, [...U, unknown]>

四則演算

NumberToTupleを使うと四則演算は下記のように定義できる

type Add<T extends number, U extends number> = [...NumberToTuple<T>, ...NumberToTuple<U>]['length']
type Sub<T extends number, U extends number> = NumberToTuple<T> extends [...NumberToTuple<U>, ...infer S] ? S['length'] : never
type Mul<T extends number, U extends number> = T extends 0 ? 0 : U extends 0 ? 0 : Add<T, Mul<T, Sub<U, 1> extends never ? 0 : Sub<U, 1>>>
type Div<T extends number, U extends number> = T extends 0 ? 0 : U extends 0 ? never : Sub<T, U> extends never ? 0 : Add<1, Div<Sub<T, U> extends never ? 0 : Sub<T, U>, U>>

剰余

FizzBuzzの方には剰余の計算が必要なので剰余も定義する

type Mod<T extends number, U extends number> = Sub<T, U> extends never ? T : Mod<Sub<T, U>, U>

FizzBuzz

剰余を使用すれば下記のようにFizzBuzzが定義できる。

type FizzBuzz<T extends number> = Mod<T, 15> extends 0 ? 'FizzBuzz' : Mod<T, 5> extends 0 ? 'Buzz' : Mod<T, 3> extends 0 ? 'Fizz' : T

配列を入力して、FizzBuzzを適用して返す場合は下記のようになる。

type FizzBuzzList<T extends number[]> = T extends [] ? [] : T extends [infer X, ...(infer XS)] ? [FizzBuzz<X extends number ? X : never>, ...FizzBuzzList<XS extends number[] ? XS : []>] : never

type FizzBuzzList1_15 = FizzBuzzList<[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]> // [1, 2, 'Fizz', 4, 'Buzz', 'Fizz', 7, 8, 'Fizz', 'Buzz', 11, 'Fizz', 13, 14, 'FizzBuzz']

フィボナッチ数

フィボナッチ数の定義を再帰で宣言的に記述ではなく、型Uという計算のキャッシュを使った末尾再帰での実装ですがT番目のフィボナッチ数を返す型は下記のようになる。

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>]> : 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]>

さいごに

数値演算に配列の長さを使用したNumberToTupleではNumberToTuple<46>, FibonacciではFibonacci<11>からエラーが出てしまって大きい数値を扱えないので残念ですが、TypeScriptのConditionalTypeは面白いなと思いました。
型って面白い。