Առաջադեմ տիպային մակարդակի թվաբանության կառուցում TypeScript-ում, մաս 2
Սա TypeScript-ում առաջադեմ "Add" և "Subtract" տիպերի կառուցման մեր արկածի երկրորդ և վերջին փուլն է։
Սա առաջադեմ Add և Subtract տիպերի կառուցման մեր արկածի երկրորդ և վերջին մասն է, որոնք աշխատում են և դրական, և բացասական ամբողջ թվերի հետ՝ մինչև բացարձակապես անհեթեթ վերին սահմանը՝ 9007199254740991 (Number.MAX_SAFE_INTEGER) 😅.
Add<-123, -52>; // -175
Add<123, -52>; // 71
Add<-123, 52> // -71
Add<123456789, 9988776655>; // 10112233444
Add<9007199254740989, 2>; // 9007199254740991
Մենք արդեն կառուցել ենք MinusOne և PlusOne տիպերը, որոնք թույլ են տալիս ավելացնել և նվազեցնել ցանկացած թվային լիտերալ տիպ.
MinusOne<42> // 41
MinusOne<0> // -1
PlusOne<10> // 11
// etc.
Լուծման ակնարկ
Կսկսենք լուծումը նկարագրելով կեղծկոդով։ Դրանից հետո այն կբաժանենք ավելի փոքր ենթախնդիրների և յուրաքանչյուրը կիրականացնենք որպես տիպային մակարդակի ալգորիթմ։
Որպեսզի հեշտ լինի հետևել, եզրային դեպքերը կթողնենք մի կողմ և կկենտրոնանք երկու դրական թվերի գումարման հիմնական խնդրի վրա.
123 + 42
Քանի որ արդեն ունենք PlusOne, առաջին ակնհայտ միտքն է PlusOne-ը ռեկուրսիվ կերպով կիրառել 123-ի վրա 42 անգամ։ Դա կաշխատեր վերևի օրինակի համար, բայց TypeScript-ը ռեկուրսիվ կանչերը սահմանափակում է 1000 խորությամբ, իսկ մենք ուզում ենք գումարել 1000-ից շատ ավելի մեծ թվեր։ Մեզ պետք է ավելի խելացի մոտեցում։
Եկեք գումարմանը նայենք այլ տեսանկյունից. որևէ թվին 123 գումարելը նշանակում է երեք անգամ գումարել 1, հետո երկու անգամ գումարել 10 և վերջում մեկ անգամ գումարել 100։ Ընդհանուր առմամբ, յուրաքանչյուր թիվ կարելի է գրել որպես 10-ի աստիճանների գումար, օրինակ.
|---------------------------------------|
| |---------------| |
| | | |
1234 = 4 * 10^0 + 3 * 10^1 + 2 * 10^2 + 1 * 10^3
| |---| |
| |
|---------------------------|
Թվերը այսպես տրոհելը թույլ է տալիս գումարել կամայականորեն մեծ թվեր (քանի դեռ դրանք տեղավորվում են JavaScript-ի թվերի տիրույթում)՝ առանց TypeScript-ի ռեկուրսիայի սահմանին հասնելու։ Շատ մոտավոր հիմնավորումը հետևյալն է. MAX_SAFE_INTEGER-ն ունի քսանից մի քանի ավելի թվանշան, ասենք 30, որը սահմանափակում է «արտաքին ցիկլը»։ Ներքին ցիկլը սահմանափակված է 10-ով, քանի որ կա 10 թվանշան։ Այսպիսով, նույնիսկ ամենավատ դեպքում չպետք է գերազանցենք 30 * 10 = 300 (< 1000) ներդրված ռեկուրսիվ կանչերը։
Լուծման ուրվագիծը ձեռքի տակ ունենալով՝ եկեք այն կառուցենք քայլ առ քայլ։
Ստեղծել 10-ի k աստիճանը
Կսկսենք ավելի հեշտ ենթախնդրից։ Ահա 10-ի առաջին մի քանի աստիճանները.
10^0 = 1
10^1 = 10
10^2 = 100
10^3 = 1000
...
Սա մեզ ասում է, որ 10-ը k աստիճանով, բնական k-ի համար, պարզապես 1 է, որին հաջորդում են k զրոներ.
type Create10ToPower<Power extends number>
= ParseInt<`1${Repeat<"0", Power>}`>;
Դեկլարատիվ ծրագրավորումը հիանալի չէ՞։ Սակայն մենք դեռ չունենք Repeat ֆունկցիայի սահմանումը, ուստի եկեք գրենք այն.
type Repeat<
T extends string,
n extends number,
acc extends string = ""
> = n extends 0 ? acc : Repeat<T, MinusOne<n>, `${acc}${T}`>;
Սկսում ենք դատարկ կուտակիչով (acc), և քանի դեռ n-ը մեծ է 0-ից, Repeat-ը կանչում ենք ռեկուրսիվ՝ նվազեցրած n-ով և կուտակիչին կցված T-ով (կրկնվող տողով)։ Երբ n-ը հասնում է 0-ի, պարզապես վերադարձնում ենք կուտակիչը։ Նկատեք, որ MinusOne-ն արդեն օգտակար է ապացուցվում նույնիսկ օժանդակ տիպերի ներսում։
Այնքան էլ դժվար չէ, չէ՞։ Հուսով եմ՝ սա ձեզ տաքացրեց, որովհետև կամայական թվին 10^k գումարելը բոլորովին այլ պատմություն է 😅
Կամայական թվին 10^k գումարելը
n թվին 10^k գումարելը պահանջում է երեք դեպքի մշակում.
k-ն 0 է10^k > n10^k <= n
Երբ k-ն 0 է
Այս դեպքը աննշան է. 10^0-ն հավասար է 1-ի, ուստի պարզապես վերադարձնում ենք PlusOne<n>։
Երբ 10^k > n
Այս դեպքը նույնպես բավական պարզ է, ահա պատկերացումը.
1000000
+ 123
-------
1000123
Թող d-ն նշանակի n-ի թվանշանների քանակը։ Այդ դեպքում 10^k + n-ը ներկայացնող տողը պարզապես 10^k-ն է՝ վերջին d զրոները փոխարինված n-ով։ Այլ կերպ ասած՝ 1, հետո k - d զրո, հետո n-ի տողային տեսքը.
1 000 000 <- 6 0s, so k is 6
+ 123 <- 3 digits, so d is 3
---------
1 000 123
^^^ ^^^
k-d d
Որպեսզի իրականացման մեջ հանումի կարիք չունենանք, կընտրենք առաջին ձևակերպումը (վերջին d զրոները փոխարինված n-ով)։ Դա նշանակում է 10^k-ի վերջին d թվանշանները հեռացնել և դրանց տեղը դնել n-ը.
type AddBiggerPowerOf10ToN<
PowerOf10 extends string,
N extends string
> = `${ReverseString<Drop<ReverseString<PowerOf10>, LengthOfString<N>>>}${N}`;
Դրա համար մեզ պետք են երկու օժանդակ տիպ՝ LengthOfString և Drop.
export type LengthOfString<
S extends string,
len extends number = 0
> = S extends `${infer _}${infer rest}`
? LengthOfString<rest, PlusOne<len>>
: len;
type Drop<S extends string, N extends number> = N extends 0
? S
: S extends `${infer _}${infer Rest}`
? Drop<Rest, MinusOne<N>>
: S;
Երբ 10^k <= n
Այս դեպքի իրականացումն ավելի զվարճալի է։ Կրկին մի քանի օրինակ կօգնեն պատկերացնել այն.
123 456
+ 100
------
123 556
1234 56
+ 1 00
------
1235 56
Թող m-ը լինի այն թիվը, որ ստանում ենք n-ից վերջին k թվանշանները հեռացնելով։ Վերևի պատկերացումները ցույց են տալիս, որ արդյունքը պարզապես PlusOne<m> է՝ n-ի վերջին երկու թվանշաններով կցված.
type AddSmallerPowerOf10ToN<Power extends number, N extends number> = ParseInt<
ReverseString<`${Take<ReverseString<`${N}`>, Power>}${InternalPlusOne<
Drop<ReverseString<`${N}`>, Power>
>}`>
>;
Թվից տող ավելորդ փոխակերպումներից խուսափելու համար մենք կրկին օգտագործում ենք InternalPlusOne օժանդակ տիպը։
Greater-ի իրականացումը
Մնում է մեկ ենթախնդիր. ինչպե՞ս համեմատել 10^k-ն n-ի հետ՝ պարզելու համար, թե 10^k-ն մեծ է, փոքր է թե հավասար է n-ին։ Դրա համար կգրենք Greater<A extends number, B extends number> տիպը, որը հավասար է true, երբ A-ն մեծ է B-ից։
Այս պահին հավանաբար չեք զարմանա, որ տողերը կրկին մեր գործիքը կլինեն 😅։ Ահա պլանը.
- Երկու թվերը դիտարկել որպես տողեր։
- Երբ A-ն ավելի կարճ է, քան B-ն, վերադարձնել false։
- Երբ B-ն ավելի կարճ է, քան A-ն, վերադարձնել true։
- Երբ երկուսն էլ նույն երկարությունն ունեն.
- Ձախից սկսելով՝ գտնել առաջին դիրքը, որտեղ A-ն և B-ն տարբերվում են՝
aևbթվանշաններով։ - Երբ
a > b, վերադարձնել true։ - Երբ
b > a, վերադարձնել false։
- Ձախից սկսելով՝ գտնել առաջին դիրքը, որտեղ A-ն և B-ն տարբերվում են՝
isShorter տիպը բավական պարզ է.
type isShorter<
A extends string,
B extends String
> = A extends `${infer Head}${infer Rest}`
? B extends `${infer Head2}${infer Rest2}`
? isShorter<Rest, Rest2>
: false
: B extends `${infer Head2}${infer Rest2}`
? true
: false;
Նույն երկարության երկու թվերի համեմատությունն ավելի բարդ է։ Մեր բարձր մակարդակի ալգորիթմի համաձայն՝ մենք պետք է կարողանանք համեմատել թվանշանների ցանկացած զույգ։ Ես սա լուծեցի համեմատման աղյուսակով.
type GTTable = [
["=", "<", "<", "<", "<", "<", "<", "<", "<", "<"],
[">", "=", "<", "<", "<", "<", "<", "<", "<", "<"],
[">", ">", "=", "<", "<", "<", "<", "<", "<", "<"],
[">", ">", ">", "=", "<", "<", "<", "<", "<", "<"],
[">", ">", ">", ">", "=", "<", "<", "<", "<", "<"],
[">", ">", ">", ">", ">", "=", "<", "<", "<", "<"],
[">", ">", ">", ">", ">", ">", "=", "<", "<", "<"],
[">", ">", ">", ">", ">", ">", ">", "=", "<", "<"],
[">", ">", ">", ">", ">", ">", ">", ">", "=", "<"],
[">", ">", ">", ">", ">", ">", ">", ">", ">", "="]
];
type GTSameLength<
A extends string,
B extends string
> = A extends `${infer DigitA extends number}${infer RestA}`
? B extends `${infer DigitB extends number}${infer RestB}`
? GTTable[DigitA][DigitB] extends ">"
? true
: GTTable[DigitA][DigitB] extends "<"
? false
: GTSameLength<RestA, RestB>
: false
: false;
Ցանկացած a և b թվանշանների համար GTTable[a][b]-ին նայելը տալիս է “>”, “=” կամ “<”։
Ամեն ինչ համադրելով՝ ստանում ենք.
export type Greater<A extends number, B extends number> = InternalGT<
`${A}`,
`${B}`
>;
type InternalGT<A extends string, B extends string> = isShorter<
A,
B
> extends true
? false
: isShorter<B, A> extends true
? true
: GTSameLength<A, B>;
Plus10ToPower-ի իրականացումը
Այժմ վերևի տիպերը կարելի է միավորել մեկ Plus10ToPower տիպի մեջ, որը ցանկացած N թվին գումարում է 10-ը Power աստիճանով։
type Plus10ToPower<N extends number, Power extends number> = Power extends 0
? PlusOne<N>
: Greater<Create10ToPower<Power>, N> extends true
? ParseInt<AddBiggerPowerOf10ToN<`${Create10ToPower<Power>}`, `${N}`>>
: AddSmallerPowerOf10ToN<Power, N>;
Գումարման ալգորիթմի համար ամեն ինչ պատրաստ է։ Կարճ հիշեցում, թե ինչպես է այն աշխատում.
A-ին B գումարելու համար մենք անցնում ենք B թվի շրջված տեսքի (այսինքն՝ հետ գնալով) յուրաքանչյուր d թվանշանով և նրա i ինդեքսով և հաշվում sum += Plus10ToPower<A, i> * d։ d-ով բազմապատկելու փոխարեն մենք ռեկուրսիվ կերպով կգումարենք Plus10ToPower<A, i>-ը d անգամ։ Փոքր օժանդակ ֆունկցիան սա հեշտացնում է.
type AddPowerOf10NTimes<
sum extends number,
power extends number,
N extends number
> = N extends 0
? sum
: AddPowerOf10NTimes<Plus10ToPower<sum, power>, power, MinusOne<N>>;
Եվ ահա ամեն ինչը միասին.
type Adder<
sum extends number,
reversedDigits,
currentPower extends number = 0
> = reversedDigits extends `${infer d extends number}${infer rest}`
? Adder<AddPowerOf10NTimes<sum, currentPower, d>, rest, PlusOne<currentPower>>
: sum;
type res = Adder<50, "24">; // 92, bacause "24" is reversed "42".
Շրջված տողերի անհարմարությունը թաքցնելու համար սահմանենք SimpleAdd.
type SimpleAdd<A extends number, B extends number>
= Adder<A, ReverseString<`${B}`>>;
type res1 = SimpleAdd<42, 50>; // 92
Ինչո՞ւ SimpleAdd անունը, այլ ոչ թե պարզապես Add։ Ինչպես հիշում եք, մինչ այժմ մենք աջակցում ենք միայն երկու դրական թվերի գումարմանը։ SimpleAdd-ը բացասական թվերի հետ աշխատեցնելը հիանալի վարժություն է, և ես այն թողնում եմ ձեզ որպես մարտահրավեր։
Սկսելուն օգնելու համար ահա անհրաժեշտ քայլերի ուրվագիծը.
-
Գրեք
Subtractտիպը՝ ընդօրինակելովAdder-ը։ -
Գրեք
isNonNegativeևAbsտիպերը։ -
Գրեք իրական
Add-ը՝ ըստ այս կեղծկոդի.Add<a, b> = if a < 0 and b < 0 then `-{SimpleAdd<Abs<a>, Abs<b>>}` if a < 0 and b > 0 then Subtract<b, Abs<a>> if < > 0 and b > 0 then Subtract<a, Abs<b>> if a > 0 and b > 0 then SimpleAdd<a, b>
Շատ շնորհակալություն ընթերցելու համար։ Եթե հասել եք մինչև այստեղ, ուրախ կլինեմ կարդալ այս հոդվածի մասին ձեր կարծիքը մեկնաբանություններում։ Եվ ինչպես միշտ, եթե գրառումը ձեզ դուր եկավ, մտածեք մեր տեղեկագրին բաժանորդագրվելու և այն ձեր ընկերներին ու գործընկերներին փոխանցելու մասին։