🐱

あなたはTypeScriptの"型"で足し算、できますか？

2021/12/22に公開

React

Sansan Advent Calendar 2021 22日目の記事です🎄

皆さん、突然ですがTypeScript(以下TS)で足し算したことありますか？

const sum = 1 + 1 // 2

簡単ですね。

では”型”で足し算をしたことがありますか？

type sum = 1+1 // ';' expected.

ご覧の通り、残念ながらTSの型上で四則演算は実装されていないようです。残念(?)。
じゃあもう型で足し算はできないの？😭

安心してください。今回は型でそれを実現する方法を模索していきます。

配列長で計算してみる

TSでは、配列の型から長さを取得をすることができます。

type SampleArray = [1,2,3,4,5]
type Length = SampleArray['length'] // 5

なんと！では簡単に足し算が実装できそうな雰囲気です。
計算したい長さの配列を用意し、その配列を結合後長さを測れば良さそうです。

では、まず与えられた数値に対してその長さの配列を生成する型を作ってみましょう。
イメージはこんな感じです。

type NumToArrray<A extends number> = /** 配列を生成する処理 **/

type Sum<A extends any[], B extends any[]> 
	= [...A, ...B]['length']

では、NumToArrrayを実装しましょう。結果は以下のようになります。

type NumToArrray<A extends number, Result extends any[]= []>
    = Result['length'] extends A
        ? Result
        : NumToArrray<A, [...Result, 0]>

type SampleArray = NumToArrray<4> // [0, 0, 0, 0]

いきなりこれをみても理解できない人がほとんどだと思われるので一つ一つ解説します。
まず、extendsの使い方についてです。これはTypeScript2.8から導入されたConditional Typesと呼ばれるもので、型が合致しているかどうかで条件分岐が可能です。

type IsString<T> = T extends string ? true : false
type A = IsString<'123'> // type A = true
type B = IsString<123> // type B = false

これにより、「指定した長さの配列ができているか」のチェックはできそうです。

では次に配列を生成する方法です。実はTSの型は、再帰処理を行うことができます。

type Recursive<A extends any[] = []> = Recursive<[...A, 1]>

このままだと無限に再帰をしてしまうため、抜けるための条件が必要です。今回は指定の長さの配列を生成したいので、Conditional Typesを用いて、配列の長さが指定した長さになったかチェックを行います。以上を踏まえると先ほどの型が理解できるようになったと思います。

type NumToArrray<A extends number, Result extends any[]　= []>
    = Result['length'] extends A
        ? Result
        : NumToArrray<A, [...Result, 1]>

やりました！これで足し算ができそうです！確認してみます。

type SumUseArray<A extends unknown[], B extends unknown[]> 
    = [...A, ...B]['length']
    
type Sum<A extends number, B extends number>
    = SumUseArray<NumToArrray<1>, NumToArrray<1>>

type Result = Sum<1,1> // 2

無事 1 + 1 = 2ができています！成功です！

配列長での足し算サンプル

TS Playground

type NumToArrray<A extends number, Result extends any[]= []>
    = Result['length'] extends A
        ? Result
        : NumToArrray<A, [...Result, 0]>

type SampleArray = NumToArrray<4> // [0, 0, 0, 0]

type SumUseArray<A extends unknown[], B extends unknown[]> 
    = [...A, ...B]['length']
    
type Sum<A extends number, B extends number>
    = SumUseArray<NumToArrray<A>, NumToArrray<B>>

type Result = Sum<1, 1> // 2

深さという""壁""

さて、我々はTSで足し算を実現できてしまいました。このくらい余裕でしたね。
では、もっと大きい数の計算をしてみましょう。

「おぼろげながら浮かんできたんです　1000という数字が」

type Result = Sum<1000, 1>
                  ^^^^
                  Type instantiation is excessively deep 
		  and possibly infinite.

ムム...Type instantiation is excessively deep and possibly infinite. と怒られてしまいました。どういうことでしょう？

実は、TSには再帰をする上限が設定されており、残念ながら通常の設定ではそれ以上の深さを潜ることはできないのです...。(※オブジェクトのプロパティを利用して再帰上限を突破するhackもありますが、本質的な解決にならない為ここでは割愛します^[1])
また、深さの上限はTSのバージョンによって異なりますが、バージョン4.5.3現在では最大の深さは999です(バージョン4.4.3の時の深さは46でした)。

深さを減らす工夫を考える

じゃあ大きい数の計算はできないの？　😢と思ったそこのあなた。大丈夫です。まだ希望はあります。おそらく、この記事を読んでいる方が確実に一回はやったことがあるであろう、ある計算方法を使うことで深さを極力減らして計算を行うことができます。

勘の良い方はもうお気づきですよね？そう、筆算です。
２つの値同士の足し算を行う場合、筆算は最も有効な計算方法です。釈迦に説法だとは思いますが、実際に筆算を行う時の計算プロセスを見てみましょう。以下のような問題があるとします。

筆算1

この時、筆算では一桁同士の足し算を行い、二桁以上になった場合にはその数値を繰り越して次の桁に上げる、というステップを踏みます。

AとBの一桁目同士を加算する
繰り上げがある場合には次の桁を加算した結果に+1する
繰り上げとA、Bの桁がなくなるまでこれを繰り返す

つまり、先ほどの例に当てはめると

6 + 8 = 14 (1繰り上げ、計算結果："4")
4 + 5 + 1 = 10(1繰り上げ、計算結果："04")
0 + 0 + 1 = 1(計算結果："104")

つまり、最大でAまたはBの最大桁数+1の深さ(上記の例だと深さ3)で、足し算が実現できそうです！🎉

筆算を実現する

さあ、タネが分かってしまえばあとは実装するだけです。ここからは細かいですが、実際にTSで筆算を実装していくステップを詳細に記述していきます。

一桁同士の和

まずは一桁同士の和の計算をしてみましょう。一桁同士程度の計算なら、先ほど説明したSumUseArrayが使えます。しかし、あれは配列の生成過程で再帰を必要とするため、桁数が大きい計算で深さを無駄に消費してしまいます。なのでより深さを消費しない方法を用います。

type AddTable = [
  [0,  1,  2,  3,  4,  5,  6,  7,  8,  9],
  [1,  2,  3,  4,  5,  6,  7,  8,  9, 10],
  [2,  3,  4,  5,  6,  7,  8,  9, 10, 11],
  [3,  4,  5,  6,  7,  8,  9, 10, 11, 12],
  [4,  5,  6,  7,  8,  9, 10, 11, 12, 13],
  [5,  6,  7,  8,  9, 10, 11, 12, 13, 14],
  [6,  7,  8,  9, 10, 11, 12, 13, 14, 15],
  [7,  8,  9, 10, 11, 12, 13, 14, 15, 16],
  [8,  9, 10, 11, 12, 13, 14, 15, 16, 17],
  [9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
]
type A = AddTable[0][0] // 0
type B = AddTable[5][8] // 13
type C = AddTable[9][9] // 18

上記のAddTableという型は二次元配列のindexと、その要素が計算結果になっている型です。一桁同士の和は高々10x10=100パターンしかないので、配列で表現すれば、再帰せずとも計算結果を得ることができます。

一桁ずつの値の取り出し

TSの型では、数値の一桁目を取得といったことは簡単にはできず、一工夫する必要があります。
型は数値の操作に柔軟ではないので、受け取った数値を文字列に変換し、その文字列を加工することにします。数値 => 文字列への変換はTypeScript4.1で導入されたTemplate Literal^[2]を使うと容易です。

type ToString<A extends number | string> = `${A}`;
type StringNumber = ToString<123>; // "123"

次に一桁の取り出しですが、文字列を一文字ずつsplitした配列にし、その配列の要素の末尾を適宜取り出していく形にすると、次の桁への移行などが綺麗にかけそうです。まずは、文字列から先頭の文字を抜き出す型を書きます。

type GetFirstString<S extends string> =
    S extends `${infer First}${infer Rest}` ? First : ''

type A = GetFirstString<'abc'> // 'a'
type B = GetFirstString<''> // ''

ここで初登場したinferというキーワードがあります。inferは、先ほど説明したConditional Typesと組み合わせることで、対象から条件にマッチした型を取り出すことができます。先ほどの例でいうと受け取った文字列に対してFirstとRestに文字列を分割できる場合には、適当な文字列がFirstとRestに渡されます。テンプレートリテラルでマッチングした場合には、最初のFirstには対象の文字列の1文字目、RestにはFirstを除いた残りの文字列が入ります。

このように、inferを使えば文字列を一文字ずつ分解できるので、文字列 => 配列への変換は以下の型で実現できます。

type SplitString<A extends string, Result extends string[] = []> = 
    A extends `${infer First}${infer Rest}` 
        ? SplitString<Rest, [...Result, First]>
        : Result

type StringArray = SplitString<ToString<2034>> // ['2', '0', '3', '4']

文字列を配列に変換できたので、あとはその配列の末尾の要素を取り出せば一桁目を抜き出すことができます。配列の末尾の取得は、先ほどと同様inferキーワードを使うことで実現できます。

type GetLastOfArray<A extends string[]> = A extends [...infer _, infer Last] 
    ? Last extends string
        ? Last
        : null
    : null
    
type A = GetLastOfArray<["1", "2", "3"]> // "3"
type B = GetLastOfArray<["1"]> // "1"
type C = GetLastOfArray<[]> // "null"

[...infer _, infer Last]は、Lastに配列の末尾の要素、_にはそれ以外の要素が入ります。文字列のときとは少し異なり配列の型推論では、スプレッド演算子をうまく用いることで任意の位置の要素を取得することができます。

再帰で筆算を表現する

一桁ずつの値の取り出しと、一桁同士の和の計算に成功したので、後はこれらを合体させれば筆算を再現することができそうです。いきなり完成系を出すと流石に混乱するので、ステップに分けて筆算を実装していきます。

STEP1. 与えられた数値の一桁目だけを足してみる

先ほど作成した型を用いて、一桁目だけを足す型を作ってみます。

type StringOneDigitMap = {
    "0": 0,
    "1": 1,
    "2": 2,
    "3": 3,
    "4": 4,
    "5": 5,
    "6": 6,
    "7": 7,
    "8": 8,
    "9": 9
}

type StringOneDigit = keyof StringOneDigitMap

type StringOneDigitToNum<A extends string | null> 
    = A extends StringOneDigit 
        ? StringOneDigitMap[A]
        : 0

type AddStringOneDigits<A extends string | null, B extends string | null> 
    = ToString<AddTable[StringOneDigitToNum<A>][StringOneDigitToNum<B>]>;

type Add_Step1<A extends string[], B extends string[]>
    = AddStringOneDigits<GetLastOfArray<A>, GetLastOfArray<B>>
    
type Result = Add_Step1<SplitString<ToString<123>>, SplitString<ToString<456>>>
// '9' ('3' + '6')

STEP1. 解説

StringOneDigitMap

String => Numberに変換する型。AddTableの二次元配列には数値でしか参照できないので文字列になっている数字をnumber型に変換する。

StringOneDigit

"0" - "9"の型、すこし厳密にする。

StringOneDigitToNum

該当しないstringやnullは一律0にする。

AddStringOneDigits

一桁同士の和。先ほど作ったAddTableの結果を吐き出しているだけ。

Add_Step1

渡された数値の末尾の値(GetLastOfArray)を足した値を返す。

これで、渡された数値の一桁目を計算することができました。

STEP2. 桁上がりを考慮せずに全ての桁を足してみる

いきなり桁上がりを考慮すると複雑なので、まずは考慮せずに全ての桁を足すだけの型を実装してみます。イメージとしては、104+109 =203(繰り上げがないから)ができればOKです。

type PopLast<A  extends string[]> = A extends [...infer Rest, infer _] 
    ? Rest extends string[] 
        ? Rest
        : []
    : []

type Add_Step2<
    A extends string[],
    B extends string[],
    Result extends string = '',
    Sum extends string | null 
    　　　　= AddStringOneDigits<GetLastOfArray<A>, GetLastOfArray<B>>,
    SplitSum extends StringOneDigit[] | null
    　　　　= Sum extends string ? SplitString<Sum>: null
> =
    SplitSum extends StringOneDigit[]
        ? Add_Step2<PopLast<A>, PopLast<B>, `${GetLastOfArray<SplitSum>}${Result}`>
        : Result

STEP2. 解説

PopLast

配列の最後の要素を除いた配列を返す型。要素がない場合は空配列が返る
再帰的に桁を見ていくとき、最後に見た桁を削除して次の計算にまわすために必要。

Add_Step2

Genericsは以下の意味を持つ。呼び出し側はAとBだけを渡せば良い。

A, B: 計算対象
Result: 計算結果を保持するGenerics
Sum: AとBの一桁目の計算結果、string
SplitSum: Sumの結果を配列に変換する。GetLastで最後の要素(=計算結果の下一桁)を取得する目的

Conditional Typesを用いて数値の配列ではない場合にはそのまま保持した計算結果を返し、数値の配列の場合は再帰を継続。

２回目以降の再帰のGenericsには以下の情報が入る。

PopLast<A>, PopLast<B>: 末尾の桁を削除した数字の文字列の配列
`${GetLast<SplitSum>}${Result}`: SplitSumで計算結果の末尾を、現在のResultの前にくっつけた値

再帰を実行した時のGenericsの変遷は以下のようになる。

A = 104, B = 109;
/**
 * 深さ=1
 * 呼ばれる型=Add_Step2<["1", "0", "4"], ["1", "0", "9"]>
**/
// AとBの一桁目を計算し(4+9=13)、次の計算に渡す
// A,Bの末尾の要素(それぞれ"4", "9")を削除
// Resultには"13"の一桁目の"3"を追加
A: ["1", "0", "4"]
B: ["1", "0", "9"]
Result: ""
Sum: "13"
SplitSum: ["1", "3"]

/**
 * 深さ=2
 * 呼ばれる型=Add_Step2<["1", "0"], ["1", "0"], "3">
**/
// AとBの一桁目を計算し(0+0=0)、次の計算に渡す
// A,Bの末尾の要素(それぞれ"0", "0")を削除
// Resultには"0"を先頭に追加

A: ["1", "0"]
B: ["1", "0"]
Result: "3"
Sum: "0"
SplitSum: ["0"]

/**
 * 深さ=3
 * 呼ばれる型=Add_Step2<["1"], ["1"], "03">
**/
// AとBの一桁目を計算し(1+1=2)、次の計算に渡す
// A,Bの末尾の要素(それぞれ"1", "1")を削除
// Resultには"2"を先頭に追加
A: ["1"]
B: ["1"]
Result: "03"
Sum: "2"
SplitSum: ["2"]

/**
 * 深さ=4
 * 呼ばれる型=Add_Step2<[], [], "203">
**/
// AとBが空なので計算なし、Resultを返す

A: []
B: []
Result: "203"
Sum: null
SplitSum: null

==> 結果: "203"

104+109=203が計算できました！（桁上がりを考慮していないので計算自体は間違いです）
Genericsを駆使した型なのでどんどん複雑になってきました🙃

Tips: Genericsに計算結果を書く方法

上記の例では、Genericsにいろいろな計算結果を保存しています。型内で複雑に整形した型を複数回用いる場合(上記だとSplitSumがそれにあたる)、変数代わりにGenericsを使うことでコードの可読性と計算量を下げることができます。

STEP.3 桁上がりも考慮して計算してみる

さあ、残すは桁上がりを計算するだけです！
さて、二つの値の足し算の場合、桁上がりする数はかならず1を超えない性質があります。
(一桁の最大値は9なので、9+9は18であり、直前に桁上がりしていたと仮定したとしても、その合計値は19)

つまり、桁上がりをしたかどうかのフラグを持ち、フラグがある場合には計算結果に+1すれば意図した計算ができそうです。実際に桁上がりを考慮した型は以下のようになります。

type Carry<
    A extends string | null,
    Split = A extends string ? SplitString<A>: null
> = Split extends StringOneDigit[]
        ? Split['length'] extends 2
            ? `${Split[0]}${AddStringOneDigits<Split[1], '1'>}`
            : `${AddStringOneDigits<Split[0], '1'>}`
        : A

type _Add<
    A extends string[],
    B extends string[],
    Result extends string = '',
    Carrying extends boolean = false,
    _Sum extends string | null 
        = AddStringOneDigits<GetLast<A>, GetLast<B>>,
    Sum extends string | null 
        = Carrying extends true ? Carry<_Sum> : _Sum,
    SplitSum extends StringOneDigit[] | null 
        = Sum extends string ? SplitString<Sum>: null
> = SplitSum extends StringOneDigit[]
        ? _Add<
            PopLast<A>,
            PopLast<B>,
            `${GetLast<SplitSum>}${Result}`,
	    // 二桁なら桁上げする必要があるのでフラグを立てる
            SplitSum['length'] extends 2 ? true : false
        >
	// 最後に桁上がりがあったらアタマに1を付ける
        : Carrying extends true
            ? `1${Result}` 
            : Result

STEP3. 解説

Carry

桁上がりを計算する型。渡された文字列(数値)に+1した値を返す。複数桁になった場合の考慮が必要なため式が複雑になっているが、やっていることは至ってシンプルでAddStringOneDigitsを使って+1した結果を返す。

type Result = Carry<"18"> // "19"
type Result = Carry<"1"> // "2"

Add

先ほどのAdd_Step2にCarryingと、Carryingしてた場合の計算結果を保持するためのGenericsが追加した。あとは、再帰時に渡す値として、SplitSumの長さが2(=繰り上げ)かどうかをCarringフラグとして渡している。

再帰を実行した時のGenericsの変遷は以下のようになる。

A = 104, B = 109;
/**
 * 深さ=1
 * 呼ばれる型=_Add<["1", "0", "4"], ["1", "0", "9"]>
**/
// AとBの一桁目を計算し(4+9=13)、次の計算に渡す
// A,Bの末尾の要素(それぞれ"4", "9")を削除
// Resultには"13"の一桁目の"3"を追加
// Carryingフラグはtrueにする
A: ["1", "0", "4"]
B: ["1", "0", "9"]
Result: ""
Carrying: false
_Sum: "13"
Sum: "13"
SplitSum: ["1", "3"]

/**
 * 深さ=2
 * 呼ばれる型=_Add<["1", "0"], ["1", "0"], "3", true>
**/
// AとBの一桁目と、桁上がりを計算し(0+0+1=1)、次の計算に渡す
// A,Bの末尾の要素(それぞれ"0", "0")を削除
// Resultには1を追加
// Carryingフラグはfalse
A: ["1", "0"]
B: ["1", "0"]
Result: "3"
Carrying: true
_Sum: "0"
Sum: "1"
SplitSum: ["1"]

/**
 * 深さ=3
 * 呼ばれる型=_Add<["1"], ["1"], "13", false>
**/
// AとBの一桁目を計算し(1+1=2)、次の計算に渡す
// A,Bの末尾の要素(それぞれ"1", "1")を削除
// Resultには2を追加
// Carryingフラグはfalse
A: ["1"]
B: ["1"]
Result: "13"
Carrying: false
_Sum: "2"
Sum: "2"
SplitSum: ["2"]

/**
 * 深さ=4
 * 呼ばれる型=_Add<[], [], "213", false>
**/
// AとBが空なので計算なし、Resultを返す
A: []
B: []
Result: "213"
Carrying: false
_Sum: null
Sum: null
SplitSum: null

==> "213"

無事繰り上げを考慮した計算を型で実現することができました🎉

type add = Add<1028490312, 7264923094> // 8293413406

大きい桁同士の足し算も問題なく実行できます！
当初の配列長の手法では絶対に計算できないですね。やりました。

これであなたもTS型マスターへの道を一歩踏み出したのです。👴

番外編: 9007199254740991以上の計算

9007199254740991(Number.MAX_SAFE_INTEGER)より大きい数字を扱いたい場合、TSのNumberでは限界があります。

// 9007199254740991以上はNumberは正常に扱えない
const overMaxSafeInteger = 9007199254740993; // ❌ 9007199254740992

このように、9007199254740993を代入したはずが、TSとして認識できるのは9007199254740992になってしまいます。そのため、MAXより大きな値をGenericsで渡す場合、stringで渡すことでこれを回避します。

// stringで扱えば問題ない
type add_str = Add<"9007199254740993", "1"> // 👌　9007199254740994
type add_large = Add<"123456789123456789123456789123456789", "123456789123456789123456789123456789"> // 🌚 246913578246913578246913578246913578

試したい方のためにTS Playgroundも用意しました。

おわりに

今回は腕試し的に加算の型でしたが、掛け算、割り算になってくるともっと高難易度になりそうなので時間があれば挑戦していきたいです(ゆくゆくは逆ポーランド記法とか...)。

正直、型で加算ができたところで旨味は全くないと思いますが、これをきっかけにいろいろな型の書き方、アイデアが浮かぶきっかけになれば嬉しいです。

この記事でもっと型パズルに挑戦したい！と思った方は、是非Type-Challenges^[3]にも挑戦してみてください！

脚注

Susisu氏: TypeScript の型の再帰上限を突破する裏技 ↩︎
https://www.typescriptlang.org/docs/handbook/release-notes/typescript-4-1.html ↩︎
型の様々な問題を掲載しているサイト。コミュニティも活発で定期的に新しい問題が追加されている。日本語にも対応✅ ↩︎