۱۰ - ۱۱تعاریف

فولد یا fold نوعی تابعِ سطح بالا هست که با داشتن یه تابع برای انباشته کردن نتایج، و یه ساختار داده‌ی بازگشتی، مقدارِ انباشته شده رو برمی‌گردونه. معمولاً در کنارِ اون تابع (که قابلیت ترکیبِ تایپ‌های مقادیر داخلِ ساختار داده، و مقدارِ انباشته شده رو داره) یه "مقدار اولیه" یا start value هم تأمین میشه. برای حالت عمومی‌تر از "تخریب و حذفِ ساختار،" به کاتامورفیسم رجوع کنید.

کاتامورفیسم یا catamorphism تعمیمی از فولد برای انواعِ نوع‌داده‌‌‌هاست. با فولد میشه یه لیست رو تخریب کرد و یه تایپِ دلخواه ازش بدست آورد، اما کاتامورفیسم امکان تخریبِ ساختارِ هر نوع‌داده ای رو فراهم می‌کنه. تابعِ ‏‎bool :: a -> a -> Bool -> a‎‏ در ‏‎Data.Bool‎‏ یک مثال از کاتامورفیسم برای نوع‌داده ِ ساده و غیرمجموعه‌ای هست. تابعِ ‏‎maybe :: b -> (a -> b) -> Maybe a -> b‎‏ هم کاتامورفیسم برای ‏‎Maybe‎‏ ِه. ببینید متوجه الگویی میشین:

data Bool = False | True
bool :: a -> a -> Bool -> a

data Maybe a = Nothing | Just a
maybe :: a -> (a -> b) -> Maybe a -> b

data Either a b = Left a | Right b
either :: (a -> c)
       -> (a -> b)
       -> Either a b
       -> c

فراخوان نهایی یا tail call آخرین نتیجه‌ی یه تابع‌ه. یه مثال از فراخوان نهایی در توابعِ هسکل:

f x y z = h (subFunction x y z)
  where subFunction x y z = g x y z
-- اینجا، فراخوانِ نهایی میشه:
-- h (subFunction x y z)
-- .h یا دقیقتر بگیم، خودِ

خوداتکاییِ نهایی یا tail recursion به تابعی گفته میشه که فراخوانِ نهایی ِش خودِ تابع‌ه، و متمایز با توابعی‌ه که در فراخوان نهایی شون توابعِ دیگه‌ای رو صدا میزنن.

f x y z = h (subFunction x y z)
  where subFunction x y z = g x y z

این خوداتکاییِ نهایی نداره، ‏‎h‎‏ رو صدا میزنه، نه خودش رو.

f x y z = h (f (x – 1) y z)

هنوز خوداتکایی نهایی نداره. ‏‎f‎‏ دوباره صدا زده شده، اما نه در فراخوانِ نهایی؛ ‏‎f‎‏ یکی از آرگومان‌های نهایی در فراخوان نهایی ِ ‏‎h‎‏ ِه:

f x y z = f (x – 1) y z

حالا خوداتکاییِ نهایی داره. ‏‎f‎‏ بدون هیچ دخالتی مستقیماً خودش رو صدا میزنه.

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

خوداتکایی نهایی نداره. قبل از ادامه‌ی لیست، اختیار رو به تابع ترکیب‌کننده ِ ‏‎f‎‏ میدیم. فراخوان‌های بازگشتی در ‏‎foldr‎‏ بین ‏‎foldr‎‏ و ‏‎f‎‏ در تناوب‌اند.

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

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