۸ - ۵تقسیم اعداد صحیح از اول
اکثرِ مردم ضرب رو با حفظ جدول ضرب یاد گرفتن، معمولاً تا ۱۰×۱۰ یا ۱۲×۱۲. ولی ضرب رو میشه با تکرارِ جمع هم حساب کرد، و به طور مشابه، تقسیم صحیح رو با تفریق.
مرحله به مرحله تابعِ تقسیمِ بازگشتی رو بررسی میکنیم. اول تایپهای قابل استفاده برای این تابع رو در نظر بگیریم و ببینیم چه تایپ سیگنچر ای براش مناسبه. در تقسیمِ اعداد یه مقسوم داریم، و یه مقسومعلیه. در محاسبهی 10 / 5
با جوابِ ۲، ۱۰ مقسوم یا صورتِ کسر، ۵ مقسومعلیه یا مخرج، و ۲ خارجقسمت نام داره. پس حداقل سه عدد داریم. شاید یه تایپ سیگنچر مثل Integer -> Integer -> Integer
مناسب باشه. اگر هم بخواین خواناتر بشه، میتونین چندتا تایپِ مترادف هم تعریف کنین:
dividedBy :: Integer -> Integer -> Integer
dividedBy = div
-- تغییر میکنه به
type Numerator = Integer
type Denominator = Integer
type Quotient = Integer
dividedBy :: Numerator -- صورت
-> Denominator -- مخرج
-> Quotient -- خارجقسمت
dividedBy = div
کلیدواژه ِ type
بجای data
یا newtype
که باهاشون آشنا هستین، یه مترادفِ تایپ یا تایپ مستعار تعریف میکنه. همهشون Integer
اند، فقط با این اسمهای جدید، خواناییشون رو بیشتر کردیم.
هنوز تعریفی که میخواستیم رو برای dividedBy
ننوشتیم. یه کم جلوتر که بریم، میبینیم که تایپ سیگنچر ِ تابع هم باید تغییر بدیم. این استفاده از تایپهای مترادف (که گاهی اوقات برای خوانایی و وضوح بیشترِ تایپ سیگنچر به کار میره) رو بیشتر ممکنه در کُدهای پیچیده ببینین. برای این تابعِ نسبتاً ساده شاید لازم نبود.
در مرحلهی بعد، فرمان پایه ِ تابعمون رو بررسی کنیم. تقسیم از طریق تفریق وقتی متوقف میشه که نتیجهی تکرار تفریقها از مخرج کوچکتر بشه. اگر هم به تساوی تقسیم بشه، در صفر متوقف میشیم:
تقسیم 20 بر 4 رو حل کن
-- [2] [1]
-- [1]: مقسوم یا صورت (numerator)
-- [2]: مقسومعلیه یا مخرج (denominator)
-- جواب هم خارجقسمتِه (quotient)
4 تقسیم بر 20 == 20 - 4, 16
- 4, 12
- 4, 8
- 4, 4
- 4, 0
-- است، پس متوقف میشیم 4 کوچکتر از 0
-- 20 / 4 == 5 بار تقسیم کردیم، پس 5
ممکنه باقیمانده هم داشته باشیم. این مورد هم ببینیم:
رو حل کن 4 بر 25 تقسیمِ
4 تقسیم بر 25 == 25 - 4, 21
- 4, 17
- 4, 13
- 4, 9
- 4, 5
- 4, 1
-- کوچکتره 4 متوقف میشیم، چون از 1 در
در این مثال، شش بار ۴ رو از ۲۵ کم کردیم و ۱ باقیمانده بدست آوردیم. کل این پروسهی تقسیمِ اعداد کامل، برگردوندنِ خارجقسمت و باقیمانده رو میشه در یه تابعِ بازگشتی که تفریق و شمارش تکراری اونها رو انجام بده تعریف کنیم. چون میخوایم هم خارجقسمت و هم باقیمانده رو برگردونیم، یه توپل ِ دوتایی رو به عنوان جواب تابعِ بازگشتی ِمون تعیین میکنیم.
dividedBy :: Integral a => a -> a -> (a, a)
dividedBy num denom = go num denom 0
where go n d count
| n < d = (count, n)
| otherwise = go (n – d) d (count + 1)
با این تایپ سیگنچر، هم پلیمورفیکتر شد (Integral a => a
در مقابلِ Integer
) هم بجای یه Integer
یه توپل برمیگردونه.
اینجا از یکی از اصطلاحات رایج در هسکل به اسم تابعِ go
استفاده کردیم. به کمک این تابع که در یه عبارتِ where
تعریف میشه، تونستیم آرگومانهای بیشتری نسبت به تابع اصلی (dividedBy
) بگیریم. در این مثال، تابع اصلی دو آرگومان num
و denom
رو قبول میکنه، ولی یه آرگومان سومی هم برای شمارش تعداد دفعاتی که تفریق انجام میشه لازم داریم. اسم این آرگومان رو count
گذاشتیم (با مقدار اولیهی صفر) و هر بار که گاردِ otherwise
اجرا میشه، یکی هم به count
اضافه میشه.
تابعِ go
اینجا دو شاخه داره. حالت اول خاصتره؛ هر وقت مقسوم ِ n
کوچکتر از مقسومعلیه ِ d
بشه، خوداتکایی متوقف میشه و جوابی داده میشه. تغییر اسم آرگومانهای num
و denom
به n
و d
حائز اهمیت نیست. تابعِ go
در تعریفِ تابعِ dividedBy
به اونها اعمال شده، پس num
، denom
، و صفر در عبارتِ where
به n
، d
، و count
مقیّد شدن.
جواب میشه یه توپل از count
و آخرین مقدارِ n
. این همون فرمانِ پایه ِمونه که خوداتکایی رو متوقف میکنه و جواب نهایی رو میده.
در زیر یه نمونه از گسترشِ dividedBy
رو نوشتیم:
dividedBy 10 2
-- ،اول با روش قبلی پیش میریم
-- .ولی تعداد دفعات تفریق رو میشماریم
2 تقسیم بر 10 ==
10 - 2, 8 (بار تفریق 1)
- 2, 6 (بار تفریق 2)
- 2, 4 (بار تفریق 3)
- 2, 2 (بار تفریق 4)
- 2, 0 (بار تفریق 5)
چون عدِد آخر صفر شد، پس باقیمانده نداریم. پنج بار منها کردیم. پس 10 / 2 == 5
.
حالا با تابعِ go
:
dividedBy 10 2
go 10 2 0
| 10 < 2 = ...
-- صادق نیست، برو به شاخهی بعد
| otherwise = go (10 - 2) 2 (0 + 1)
-- هست True درواقع همون مقدار otherwise
-- ،پس اگه شاخهی اول شکست بخوره
-- .این همیشه موفق میشه
go 8 2 1
-- ،کوچکتر نیست 2 از 8
-- otherwise پس شاخهی
go (8 - 2) 2 (1 + 1)
-- n == 6, d == 2, count == 2
go 6 2 2
go (6 - 2) 2 (2 + 1)
-- ،کوچکتر نیست 2 از 6
-- otherwise پس شاخهی
-- n == 4, d == 2, count == 3
go 4 2 3
go (4 - 2) 2 (3 + 1)
-- ،کوچکتر نیست 2 از 4
-- otherwise پس شاخهی
-- n == 2, d == 2, count == 4
go 2 2 4
go (2 - 2) 2 (4 + 1)
-- ،کوچکتر نیست 2 از 2
-- otherwise پس شاخهی
-- n == 0, d == 2, count == 5
go 0 2 5
go (2 - 2) 2 (4 + 1)
-- حساب میشه n < d بالاخره شاخهی
-- حقیقت داره 0 < 2 چون
-- n == 0, d == 2, count == 5
| 0 < 2 = (5, 0)
(5, 0)
مقدارِ count
خارجقسمت میشه، و همون تعداد دفعاتیه که میشه ۲ رو از ۱۰ کم کرد. در حالتی که باقیمانده ای وجود داشته باشه، اون عدد در واقع آخرین مقدارِ مقسوم ِه که به عنوانِ باقیمانده برگردونده میشه.