LoginSignup
2
0

More than 1 year has passed since last update.

1人フロントエンドAdvent Calendar 2022Day 2
@KokiSakano(Koki Sakano)

TypeScriptで整数の足し算の型を3つの難易度で実装する

Posted at

はじめに

シンプルな整数の足し算の関数に3つの難易度で型をつけます。

const sum = (a, b) => a + b

初級

　初級はよく書かれる方法です。型で遊ぶとき以外は可読性とコストを考慮してこの実装が相応しいと考えています。TypeScriptの基礎ですのでコードに対する解説は省略します。このコードは整数でなくても動く点でも後ほど紹介する型より有利です。

type Sum = (a: number, b: number) => number;

中級

初級の例では引き算など他の関数でも同様の型を割り当てることができます。中級では返り値にnumberではなく足し算の結果の値を渡すようにします。例えばsum(1, 2）の型は3と出るようなSumを実装します。

type LengthArray<N extends number, Result extends never[] = []> =
  Result['length'] extends N
    ? Result
    : LengthArray<N, [...Result, never]>;  
type Addition<A extends number, B extends number> =
  [...LengthArray<A>, ...LengthArray<B>]['length'];
type Sum = <A extends number, B extends number>(a: A, b: B) => Addition<A, B>;

初級に比べるとかなりコード量が増えました。いくつか型を分けて定義したので一つずつ解説します。
LengthArrayは長さがNの配列を作る型です。引数であるNは利用される側から与えられる数値で、Resultは初期値が空配列のneverを格納する型です(neverである必要はないです)。この型はResultの長さがNと一致するまで再起的にLengthArrayを呼び出します。呼び出す時は元のResultにneverを追加したものを渡しループごとに成長させます。あるループのResultの長さとNが一致したらその時点のResultを返します。具体例としてNを3としてLengthArrayを呼び出すことを考えます。LengthArray<3>です。最初の呼び出しではResultは初期値の[]、一回目の呼び出しで[never]、2回目で[never, never]、三回目で[never, never, never]となって、配列の長さがNと一致します。一致したので[never, never, never]がLengthArray<3>の型として返却されます。
Additionは足し算のロジックを持った型です。TypeScriptの型は数値同士の足し算はサポートしていないので、数値から他の状態に変更させる必要があります。この型では配列の大きさを利用して足し算を行いました。渡されたAとBを先ほど紹介したLengthArrayに渡してそれぞれの長さを持った配列にします。それらをconcatした配列の長さはAとBの足し算の結果と等しいのでこれによって欲しい値を得ることができます。
Sumでは受け取ったaとbの型をそれぞれA、BとしてAdditionに代入したものを返り値として渡しています。これらを組み合わせることによって返り値が計算した結果の値となる型を実現することができました。

上級

中級の型は一見問題なさそうですが、実は無限ループと見做される可能性を孕んでいます。aまたはbに1000以上の数値を代入した場合Type instantiation is excessively deep and possibly infinite.とエラーが出ます。これは数値を配列に変換したときに再起的な処理を行なっていて、再起的な呼び出しの上限が1000であることに由来しています。上限値は過去のバージョンではもっと小さい値に設定されていましたし、今後も変化することが考えられます。さらに自分で上限値を設定することもできるので、1000という数値は参考程度にお願いします。上級ではこの問題を解決した型を作成します。

type Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

type SubOneFromDigit<D> = 
  D extends "0" ? "9"
  : D extends "1" ? "0"
  : D extends "2" ? "1"
  : D extends "3" ? "2"
  : D extends "4" ? "3"
  : D extends "5" ? "4"
  : D extends "6" ? "5"
  : D extends "7" ? "6"
  : D extends "8" ? "7"
  : D extends "9" ? "8"
  : never;

type AddOneToDigit<D> = 
  D extends "0" ? "1"
  : D extends "1" ? "2"
  : D extends "2" ? "3"
  : D extends "3" ? "4"
  : D extends "4" ? "5"
  : D extends "5" ? "6"
  : D extends "6" ? "7"
  : D extends "7" ? "8"
  : D extends "8" ? "9"
  : D extends "9" ? "0"
  : never;

type SumDigit<A extends Digit, B extends Digit, IsCarryIn extends boolean, IsCarryOut extends boolean = false> =
  IsCarryIn extends true
    ? SumDigit<AddOneToDigit<A>, B, false, A extends "9" ? true : false>
    : B extends "0" 
      ? [A, IsCarryOut]
      : SumDigit<AddOneToDigit<A>, SubOneFromDigit<B>, false, true extends IsCarryOut ? true : A extends "9" ? true : false>

type SumString<A extends string, B extends string, Result extends string = '', IsCarry extends boolean = false> = 
  '' extends A 
    ? '' extends B
      ? IsCarry extends true ? `1${Result}` : Result
      : B extends `${infer Rest}${Digit}` 
        ? B extends `${Rest}${infer T extends Digit}` 
          ? SumDigit<'0', T, IsCarry> extends [infer DigitResult extends Digit, infer DigitCarry extends boolean]
            ? SumString<'', Rest, `${DigitResult}${Result}`, DigitCarry>
            : never 
          : never 
        : never
    : '' extends B
      ? A extends `${infer Rest}${Digit}` 
        ? A extends `${Rest}${infer T extends Digit}` 
          ? SumDigit<'0', T, IsCarry> extends [infer DigitResult extends Digit, infer DigitCarry extends boolean]
            ? SumString<Rest, '', `${DigitResult}${Result}`, DigitCarry>
            : never 
          : never
        : never
      : A extends `${infer RestA}${Digit}` 
        ? A extends `${RestA}${infer T extends Digit}` 
          ? B extends `${infer RestB}${Digit}` 
            ? B extends `${RestB}${infer U extends Digit}` 
              ? SumDigit<T, U, IsCarry> extends [infer DigitResult extends Digit, infer DigitCarry extends boolean]
                ? SumString<RestA, RestB, `${DigitResult}${Result}`, DigitCarry>
                : never
              : never
            : never
          : never
        : never;
type Addition<A extends number, B extends number> = SumString<`${A}`, `${B}`> extends `${infer T extends number}` ? T : never;
type Sum = <A extends number, B extends number>(a: A, b: B) => Addition<A, B>;

数値を文字列に変換して、筆算のように1桁ずつ計算するようにしました。桁数で再起処理を行なっているので1000桁以上の数値は扱えませんが、そもそも2^53-1が整数の上限なので気にしないことにします(参考)。
この型の解説に移ります。
まず一桁の数字の型としてDigitを定義します。

Digit
type Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

次にSubOneFromDigitとしてDigitから1引いた数の定義、AddOneToDigitとして1足した数の定義をします。この型では繰り上がり、繰り下がりを考慮していません。

SubOneFromDigit & AddOneToDigit
type SubOneFromDigit<D> = 
  D extends "0" ? "9"
  : D extends "1" ? "0"
  : D extends "2" ? "1"
  : D extends "3" ? "2"
  : D extends "4" ? "3"
  : D extends "5" ? "4"
  : D extends "6" ? "5"
  : D extends "7" ? "6"
  : D extends "8" ? "7"
  : D extends "9" ? "8"
  : never;

type AddOneToDigit<D> = 
  D extends "0" ? "1"
  : D extends "1" ? "2"
  : D extends "2" ? "3"
  : D extends "3" ? "4"
  : D extends "4" ? "5"
  : D extends "5" ? "6"
  : D extends "6" ? "7"
  : D extends "7" ? "8"
  : D extends "8" ? "9"
  : D extends "9" ? "0"
  : never;

そして、SumDigitという一桁の足し算を行う型を定義しています。この型は最終的に足し算の1桁目の結果と繰り上がりの有無を配列にして送ります。Bが0になるまで再起的に呼び出され、Bを1ずつ減らしていきAを1ずつ増やすようになっています。呼び出された時にIsCarryInがtrueの時は最初にAの値を1増やします。前の桁で繰り上がりがあった場合にこれはtrueになります。再起的にSumDigitを呼び出すときに、Aが9の場合は繰り上がりするとみなしてIsCarryOutをtrueにします。IsCarryOutは一度trueになると永続的にtrueとして再起が進んでいきます。このようにすることでBが0になったときAが足し算の1桁目の結果となり、IsCarryOutが繰り上がりの有無となるのでそれらを配列にして返します。

SumDigit
type SumDigit<A extends Digit, B extends Digit, IsCarryIn extends boolean, IsCarryOut extends boolean = false> =
  IsCarryIn extends true
    ? SumDigit<AddOneToDigit<A>, B, false, A extends "9" ? true : false>
    : B extends "0" 
      ? [A, IsCarryOut]
      : SumDigit<AddOneToDigit<A>, SubOneFromDigit<B>, false, true extends IsCarryOut ? true : A extends "9" ? true : false>

今回紹介する中で一番大きな型であるSumStringです。これは文字列で表された数値の足し算を行う型です。引数は足し算を行うAとB、途中までの結果を保存するResult、現在見ている桁数で繰り上がりが起きていることを示すフラグIsCarryです。
この方は4つの分岐に分けることができるので分けて紹介します。紹介する部分はコメントとして記述しました。
最終的にAとBが空文字列になったタイミングで繰り上がりがあれば先頭に1を加えた1${Result}、なければResultを返します。
Aだけが空文字列の時はBの最小桁の値を取得して、先ほど紹介したSumDigitのBに代入します。Aには'0'、IsCarrayはIsCarryInを代入します。そして、その結果を取得してResultを更新します。更新はSumStringを再起的に呼び出すことで行っており、Aは空文字列、Bは2桁目以降の文字列、Resultには更新後のResult、IsCarryには先ほどのSumDigitの結果DigitCarryを渡します。
Bだけが空文字列の時はAだけが空文字列の時と文字列を入れ替えただけです。
AもBも空文字列ではない時はAとBの両方の最小桁の値を取得してSubStringに渡します。以降の処理はAと同じです。
これを繰り返すと文字列同士の足し算の結果を得ることができます。例えばSumString<'987', '13'>は、文字列で'1000'を型とします。

SumString
type SumString<A extends string, B extends string, Result extends string = '', IsCarry extends boolean = false> = 
  '' extends A 
    ? '' extends B
      // AもBも空文字列の分岐
      ? IsCarry extends true ? `1${Result}` : Result
      // Aだけが空文字列の分岐
      : B extends `${infer Rest}${Digit}` 
        ? B extends `${Rest}${infer T extends Digit}` 
          ? SumDigit<'0', T, IsCarry> extends [infer DigitResult extends Digit, infer DigitCarry extends boolean]
            ? SumString<'', Rest, `${DigitResult}${Result}`, DigitCarry>
            : never 
          : never 
        : never
    : '' extends B
      // Bだけが空文字列の分岐
      ? A extends `${infer Rest}${Digit}` 
        ? A extends `${Rest}${infer T extends Digit}` 
          ? SumDigit<'0', T, IsCarry> extends [infer DigitResult extends Digit, infer DigitCarry extends boolean]
            ? SumString<Rest, '', `${DigitResult}${Result}`, DigitCarry>
            : never 
          : never
        : never
      // AもBも空文字列では無いとき分岐
      : A extends `${infer RestA}${Digit}` 
        ? A extends `${RestA}${infer T extends Digit}` 
          ? B extends `${infer RestB}${Digit}` 
            ? B extends `${RestB}${infer U extends Digit}` 
              ? SumDigit<T, U, IsCarry> extends [infer DigitResult extends Digit, infer DigitCarry extends boolean]
                ? SumString<RestA, RestB, `${DigitResult}${Result}`, DigitCarry>
                : never
              : never
            : never
          : never
        : never;

最後にAdditionです。引数を文字列化してSumStringに割り当てます。そして、結果は文字列なので数値に変換したものを結果として返します。これを中級の問題と同じようにSumの返り値に当てはめれば足し算の型が出来上がりです。

type Addition<A extends number, B extends number> = SumString<`${A}`, `${B}`> extends `${infer T extends number}` ? T : never;
2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0