۱۰ - ۹اسکن

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

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

اول تایپ‌هاشون رو ببینیم. با تایپِ فولدها مقایسه می‌کنیم که تفاوت‌شون واضح باشه:

foldr :: (a -> b -> b) -> b -> [a] -> b
scanr :: (a -> b -> b) -> b -> [a] -> [b]

foldl :: (b -> a -> b) -> b -> [a] -> b
scanl :: (b -> a -> b) -> b -> [a] -> [b]

تفاوت اصلی در لیست بودنِ خروجی‌ه (فولد هم می‌تونه خروجی لیست بده، ولی همیشه لیست برنمی‌گردونه). یعنی اسکن کاتامورفیسم نیست، و از لحاظی اصلاً فولد نیست. ولی اهمیتی نداره! تایپ‌هاشون شبیه هَمدیگه‌ست، مسیرِ پیمایشِ ستون و محاسبه‌شون هم شبیه همدیگه‌ست. این یعنی بجای حذف ستون ِ لیست، اسکن یه لیست از نتایج میده که ممکنه گاهی اوقات مفید باشه.

چند مثال از نتایجِ خروجی اسکن:

scanr (+) 0 [1..3]
[1 + (2 + (3 + 0)), 2 + (3 + 0), 3 + 0, 0]
[6, 5, 3, 0]

scanl (+) 0 [1..3]
[0, 0 + 1, 0 + 1 + 2, 0 + 1 + 2 + 3]
[0, 1, 3, 6]

scanl (+) 1 [1..3]

-- scanl بنا به تعریف
-- .بیانیه‌ی بالا رو باز می‌کنیم
= [ 1, 1 + 1
  , (1 + 1) + 2
  , ((1 + 1) + 2) + 3
  ]

-- محاسبه‌ی جمع‌ها
= [1, 2, 4, 7]

تعریفی که این زیر از ‏‎scanl‎‏ نوشتیم، در نسخه‌ی قدیمی‌ترِ کتابخونه ِ ‏‎base‎‏ برای GHC Haskell نوشته شده بود. اینجا اون تفاوت‌هایی که با نسخه‌ی فعلی‌ش داره فرقی به حال ما ندارن:

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f q ls =
  q : (case ls of
         []   -> []
         x:xs -> scanl f (f q x) xs)

در یکی از فصل‌های قبل، یه تابعِ بازگشتی نوشتیم که n-اُمین عددِ فیبوناچی رو برمی‌گردوند. بازنویسی این تابع با اسکن رو تو یه فایل انجام میدیم، چون با این تعریف یه لیست بینهایت میده (اگه دوست دارین تو REPL بارگذاری و اِجراش کنین، اما آماده باشین سریع ‏‎Ctrl + c‎‏ رو بزنین):

fibs = 1 : scanl (+) 1 fibs

با مقدار ۱ شروع می‌کنیم و به اولِ لیستی که اسکن می‌سازه cons ِش می‌کنیم. خودِ اون لیست باید بازگشتی باشه، چون همونطور که قبلاً دیدم، هر عدد فیبوناچی از جمعِ دو عدد فیبوناچیِ قبلی بدست میاد؛ اگه ‏‎(+)‎‏ رو روی یه لیستِ غیربازگشتی اسکن کنیم (با مقدار اولیه‌ی ۱) چنین جوابی می‌گیریم:

scanl (+) 1 [1..3]
[1, 1 + 1, (1 + 1) + 2, ((1 + 1) + 2) + 3]
[1,2,4,7]

در صورتی که ما دنبال چنین جوابی هستیم: ‏‎‏‎[۱,۱,۲,۳,۵,⋯]‎‏‎‏.

عدد فیبوناچی موردِ نظر

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

(!!) :: [a] -> Int -> a

آرگومان اول‌ِش لسیت، آرگومان دوم‌ش ‏‎Int‎‏، و یک المان از لیست رو برمی‌گردونه. اون ‏‎Int‎‏ اندیس ِ المان خروجی رو تعیین می‌کنه. فایل منبع ِمون رو تعریف می‌کنیم:

fibs    = 1 : scanl (+) 1 fibs
fibsN x = fibs !! x

با استفاده از ‏‎fibsN‎‏ در REPL میشه n-امین المان از نتیجه‌ی اسکن رو بگیریم:

Prelude> fibsN 0
1
Prelude> fibsN 2
2
Prelude> fibsN 6
13

کُدتون رو با توابعِ ‏‎take‎‏ و ‏‎takeWhile‎‏، یا هر تابع دیگه‌ای که دوست دارین امتحان کنین. فقط یه نکته: اگه بدونِ ‏‎take‎‏ کردن از فیلتر استفاده کنین، خیلی جواب خوبی نمیده. درسته که لیست‌تون فیلتر شده، ولی هنوز بینهایت‌ه.

تمرین‌های اسکن