۱۰ - ۳الگوهای بازگشتی

بار دیگه تابعِ ‏‎sum‎‏ رو ببینیم:

Prelude> sum [1, 5, 10]
16

قبلاً هم دیده بودیم که یه لیست می‌گیره، المان‌هاش رو با هم جمع می‌کنه و یه مقدارِ مجرد برمی‌گردونه. یه شباهت‌هایی با تابعِ ‏‎map‎‏ داره، مثل این می‌مونه که تابعِ ‏‎(+)‎‏ روی یه لیست نگاشت و با تک‌تکِ عملگرهای cons جایگزین بشه، و در نهایت یک مقدارِ مجرد برگردونه. ولی با ‏‎map‎‏ می‌تونستیم مثلاً ‏‎(+1)‎‏ رو به تک‌تکِ سلول‌‌های cons ِ لیست اعمال کنیم و نهایتاً هم یه لیستِ کامل از جواب‌ها می‌گرفتیم. میشه گفت تابعِ ‏‎sum‎‏ تلفیقی از نگاشت ِ یه تابع به یک لیست، و کاهش (یا حذف) لیست از خروجی‌ه. قبل‌تر در کتاب، این تابع رو به صورتِ بازگشتی اینطور نوشتیم:

sum :: [Integer] -> Integer
sum []     = 0
sum (x:xs) = x + sum xs

تابعِ ‏‎length‎‏ رو هم به خاطر بیاریم:

length :: [a] -> Integer
length []     = 0
length (x:xs) = 1 + length xs

شباهت‌شون رو می‌بینین؟ اگه ‏‎product‎‏ و ‏‎concat‎‏ هم مقایسه کنیم:

product :: [Integer] -> Integer
product []     = 1
product (x:xs) = x * product xs

concat :: [[a]] -> Integer
concat []     = []
concat (x:xs) = x ++ concat xs

فرمان پایه برای همه این توابع، مقدار همانی ِ تابعِ اصلی‌شونه. پس به ترتیب برای ‏‎sum‎‏، ‏‎length‎‏، ‏‎product‎‏، و ‏‎concat‎‏ مقدارِ همانی معادلِ صفر، صفر، ۱، و ‏‎[]‎‏ هست. جمعِ هر عددی با صفر، خود اون عدد رو نتیجه میده، مثلِ ۱ = ۰ + ۱، ولی برای ضرب، عددِ ۱ مقدارِ همانی ِه: ۲ = ۲ × ۱. برای الحاق ِ لیست‌ها، مقدارِ همانی یه لیست خالی میشه، مثل: ‏‎[1,2,3] ++ [] == [1,2,3]‎‏.

چیز دیگه‌ای که بین این تابع‌ها مشترکه، یک تابعِ اصلی‌ِه که با شرکت‌پذیری از راست، به صورتِ بازگشتی اعمال میشه. سَر ِ لیست محاسبه و کنار گذاشته میشه، تابع میره راست و سَر ِ بعدی رو حساب می‌کنه؛ همینطور تا آخر.