بناء عمليات حسابية متقدمة على مستوى الأنواع في TypeScript، الجزء 2
هذه هي المرحلة الثانية والأخيرة من مغامرتنا في بناء النوعين المتقدمين "Add" و"Subtract" في TypeScript.
هذا هو الجزء الثاني والأخير من مغامرتنا في بناء النوعين المتقدمين 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 إلى أي عدد
تتطلب إضافة 10^k إلى عدد n معالجة ثلاث حالات:
kيساوي 010^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). وهذا يعني إزالة آخر d من أرقام 10^k ووضع 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 العدد الذي نحصل عليه بإزالة آخر k من خانات n. توضح التصورات أعلاه أن النتيجة هي ببساطة 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، الذي يضيف 10 مرفوعًا إلى Power إلى أي عدد N!
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، نمرّ على كل رقم d مع فهرسه i في العدد B المعكوس (أي بالعودة إلى الخلف) ونحسب 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>
شكرًا جزيلًا على القراءة! إن وصلتَ إلى هنا، فيسعدني أن أقرأ رأيك في هذه المقالة في التعليقات. وكالعادة، إن أعجبك المنشور ففكّر في الاشتراك في نشرتنا الإخبارية ومشاركته مع أصدقائك وزملائك.