۸ - ۲فاکتوریل!

یکی از توابع کلاسیک و مقدماتی برای نشون دادنِ خوداتکایی در زبان‌های تابعی فاکتوریل‌ه. احتمالاً در حساب بیانیه‌ای مثل ‏‎4!‎‏ رو دیدین. اون علامت تعجب جلوی ۴ نشون دهنده‌ی تابع فاکتوریل‌ه.

بیاین ‏‎4!‎‏ رو حساب کنیم:

4! = 4 * 3 * 2 * 1
        12 * 2 * 1
            24 * 1
                24
4! = 24

از یه راه مسخره تو هسکل بنویسیم:

fourFactorial :: Integer
fourFactorial = 4 * 3 * 2 * 1

جوابِ درست میده، اما فقط یک جوابِ ممکن از ‏‎factorial‎‏ رو پوشش میده. یه کم با ایده‌آل بودن فاصله داره. می‌خوایم مفهومِِ تابع رو بیان کنیم، نه یکی از ورودی‌هاشو.

برای معرفیِ مفهومی به اسمِ فرمانِ پایه، از یه مثالِ خراب شروع می‌کنیم:

-- این کار نمی‌کنه، چون
-- .هیچ وقت محاسبه‌ش تموم نمیشه
brokenFact1 :: Integer -> Integer
brokenFact1 n = n * brokenFact1 (n - 1)

به ۴ اعمال ِش می‌کنیم ببینیم چی میشه:

brokenFact1 4 =
  4 * (4 - 1)
  * ((4 - 1) - 1)
  * (((4 - 1) - 1) - 1)
-- ... هیچ وقت تموم نمیشه

یه بیانیه‌ی بازگشتی نیاز به یه فرمانِ پایه داره تا دیگه به خودش اعمال نَشه. این رو باید خوب درک کرد تا بشه توابعِ صحیحی نوشت که به جواب میرسن. برای ‏‎factorial‎‏ اینطور میشه:

module Factorial where

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

تابع در نسخه‌ی درست شده، با فرمانِ پایه ِ ‏‎factorial 0 = 1‎‏ یه نقطه‌ی ایست پیدا کرده، ساده‌سازی‌ش هم تغییر می‌کنه:

-- تغییر می‌کنه به‌
-- n = n * factorial (n - 1)

factorial 4 =
  1 * factorial (4 - 1)

  -- محاسبه‌ی (-) اعمال شده به ۴ و ۱
  4 * factorial 3

  -- محاسبه‌ی اعمال فاکتوریل به ۳
  -- 3 * factorial (3 - 1) معادل میشه با
  4 * 3 * factorial (3 - 1)

  -- کاهشِ بتای (-) اعمال شده به ۳ و ۱
  4 * 3 * factorial 2

  -- محاسبه‌ی اعمال فاکتوریل به ۲
  4 * 3 * 2 * factorial (2 - 1)

  -- محاسبه‌ی (-) اعمال شده به ۲ و ۱
  4 * 3 * 2 * factorial 1

  -- محاسبه‌ی اعمال فاکتوریل به ۱ 
  4 * 3 * 2 * 1 * factorial (1 - 1)

  -- محاسبه‌ی (-) اعمال شده به ۱ و ۱
  -- factorial 0 = 1 می‌دونیم
  -- پس به ۱ ساده‌ش می‌کنیم
  4 * 3 * 2 * 1 * 1

  -- و بعد از محاسبه‌ی ضرب‌ها 
  24

با استفاده از مقدارِ همانی ِ تابعی که در هسته‌ی تابع‌مون به کار رفته بود (در این مورد ضرب) در فرمان پایه، کاری کردیم که اعمال ِ تابع به فرمانِ پایه، تأثیری در نتیجه‌ی اعمال‌های قبلی نداشته باشه.

نگاهی دیگه به خوداتکایی

در فصل قبل، تابعِ سطح بالا به نام ترکیب رو دیدیم. ترکیب تابع، راهی برای گره زدنِ دو (یا بیشتر) تابع به همدیگه‌ست، طوری که نتیجه‌ی اعمال ِ اولین تابع، به عنوان آرگومان به تابع بعدی داده میشه. توابعِ بازگشتی هم همین کار رو می‌کنن – نتیجه‌ی اولین اعمال ِ تابع رو به تابع بعدی میدن – فقط در مورد توابعِ بازگشتی، بجای اینکه اولین جواب به یه تابعِ دیگه داده بشه، به همون تابع داده میشه. و انقدر ادامه پیدا می‌کنه تا به فرمان پایه برسه و تموم شه.

برخلافِ ترکیب توابع که عموماً میشه اون رو مطلق و ایستا دونست، ترکیب‌های بازگشتی بی‌حد هستن. تعداد دفعاتی که تابع اعمال میشه بستگی به آرگومان‌های تابع داره، و اگه یه نقطه‌ی ایست به وضوح تعریف نشده باشه، ممکنه تا بینهایت اعمال بشه.

تایپِ ترکیب توابع رو دوره کنیم:

(.) :: (b -> c) -> (a -> b) -> a -> c

و وقتی اینطور ازش استفاده کنیم:

take 5 . filter odd . enumFrom $ 3

اولین جواب یه لیست از اعداد (ساخته شده با ‏‎enumFrom‎‏) ِه که به ‏‎filter odd‎‏ داده میشه، و اون هم فقط اعدادِ فرد رو نگه می‌داره. این لیست از اعدادِ فرد هم به ‏‎take 5‎‏ داده میشه و پنج المان اولِش جواب نهایی میشه. پس جواب‌ها از بین یک سری توابع گذرونده شدن.

خوداتکایی، همون ترکیبِ خودارجاعی ِه.^* تابع رو به یه آرگومان اعمال می‌کنیم، و بعد جواب‌ش رو به عنوان آرگومان به همون تابع میدیم، و همینطور تکرار می‌کنیم.

یه بار دیگه به تابعِ ترکیب نگاه کنیم:

(.)    :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)

در زبان‌های برنامه‌نویسی که خالصاً بر مبنای جبر لاندا نوشته شدن، مثل هسکل، محاسباتی که ساده میشن رو با یه لغت میشه توصیف کرد: اعمال کردن. هر چقدر هم با گرامرهای متفاوت در ظاهر چیز دیگه‌ای به نظر برسه، تنها کاری که میشه انجام داد، اعمال ِ توابع به آرگومان‌هاست. ترکیب توابع هم، با اینکه یه اسم و عملگر ِ مخصوص برای استفاده‌ی راحت‌تر بهش دادیم، کاری که در واقع انجام میده اینه:

(.) f g = \x -> f (g x)

خوداتکایی ِ توابع هم مشابهِ ترکیب می‌مونه. با این تفاوت که بجای تعداد ثابتی از اعمال‌ها، پایانِ اعمال ِ توابعِ بازگشتی، برمبنای جواب‌های بعدی با آرگومان‌هاشون تعیین میشه. اگه هیچ نقطه‌ی ایستی تعریف نشده باشه، جوابِ ‏‎(g x)‎‏ تا بینهایت به ‏‎g‎‏ برگردونده میشه.^*

با چندتا کُد شباهتِ این دوتا رو بیشتر می‌بینیم:

inc :: Num a => a -> a 
inc = (+1)

three = inc . inc . inc $ 0
-- همون چیز با گرامر متفاوت
three' = (inc . inc . inc) 0

اینطور که ‏‎inc‎‏ رو ترکیب کردیم، تعداد دفعاتِ اعمال ِش هم تعیین و مشخص کردیم. بدونِ نوشتنِ یه تابعِ جدید، راهی برای تغییر تعداد دفعاتِ اعمال ِ ‏‎inc‎‏ نداریم.

شاید یه تابعِ جامع که بتونه بدونِ محدودیت تابعِ ‏‎inc‎‏ رو اعمال کنه بهتر باشه؛ تعداد دفعاتِ اعمال ِ تابع رو هم به عنوانِ آرگومان بگیره:

incTimes :: (Eq a, Num a) => a -> a -> a
incTimes 0 n =
  n
incTimes times n =
  1 + (incTimes (times - 1) n)

اینجا ‏‎times‎‏ یه متغیره که تعداد دفعاتِ اعمال ِ تابعِ افزاینده (که اینجا دیگه به جای استفاده از ‏‎inc‎‏، با "۱ بعلاوه‌ی" در بدنه‌ی تابع نوشتیم) به آرگومان ‏‎n‎‏ رو مشخص می‌کنه. اگه بخوایم صفر بار اعمال بشه، خودِ ‏‎n‎‏ رو برمی‌گردونه. در غیر اینصورت، هر چند بار که گفته باشیم تابع اعمال میشه:

Prelude> incTimes 10 0
10
Prelude> incTimes 5 0
5
Prelude> incTimes 5 5
10

-- به نظر آشنا نمیاد؟

در چنین تابعی، خطرِ خوداتکایی ِ بی‌پایان به حداقل میرسه، چون تعداد دفعاتِ اعمال ِ تابع یکی از آرگومان‌های خودِ تابع‌ه. یه نقطه‌ی ایست هم براش تعریف کردیم: وقتی ‏‎(times - 1)‎‏ مساویِ صفر بشه، ‏‎n‎‏ رو برمی‌گردونه و دیگه تابع اعمال نمیشه.

تابعِ ‏‎incTimes‎‏ رو میشه تجرید هم کرد:

applyTimes :: (Eq a, Num a) =>
               a -> (b -> b) -> b -> b
applyTimes 0 f b = b 
applyTimes n f b = f (applyTimes (n-1) f b)

incTimes' :: (Eq a, Num a) => a -> a -> a
incTimes' times n = applyTimes (+1) n

حالا با این کار، ترکیب در ‏‎applyTimes‎‏ رو میشه واضح‌تر نشون داد:

applyTimes :: (Eq a, Num a) =>
               a -> (b -> b) -> b -> b
applyTimes 0 f b =
  b 
applyTimes n f b =
  f . applyTimes (n-1) f $ b

انقدر تابعِ ‏‎f‎‏ رو با ‏‎applyTimes (n-1) f‎‏ به صورتِ بازگشتی ترکیب می‌کنیم تا ‏‎n‎‏ به صفر برسه.

آنتراکت: تمرین

مراحلِ محاسبه‌ی بیانیه‌ی زیر رو یادداشت کنین. شاید با نسخه‌ای که از ‏‎(.)‎‏ استفاده نمی‌کنه پیش برین بهتر باشه.

applyTimes 5 (+1) 5