۸ - ۵تقسیم اعداد صحیح از اول

اکثرِ مردم ضرب رو با حفظ جدول ضرب یاد گرفتن، معمولاً تا ۱۰×۱۰ یا ۱۲×۱۲. ولی ضرب رو میشه با تکرارِ جمع هم حساب کرد، و به طور مشابه، تقسیم صحیح رو با تفریق.

مرحله به مرحله تابعِ تقسیمِ بازگشتی رو بررسی می‌کنیم. اول تایپ‌های قابل استفاده برای این تابع رو در نظر بگیریم و ببینیم چه تایپ سیگنچر ای براش مناسبه. در تقسیمِ اعداد یه مقسوم داریم، و یه مقسوم‌علیه. در محاسبه‌ی ‏‎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‎‏ خارج‌قسمت میشه، و همون تعداد دفعاتیه که میشه ۲ رو از ۱۰ کم کرد. در حالتی که باقیمانده ای وجود داشته باشه، اون عدد در واقع آخرین مقدارِ مقسوم ِه که به عنوانِ باقیمانده برگردونده میشه.