۱۰ - ۲به جمع فولدشناس‌ها بیاین

با نگاهی مختصر به ‏‎foldr‎‏ (که خلاصه‌ی فولد از راست هست) شروع می‌کنیم. در لیست‌ها اکثراً از این فولد استفاده میشه. شاید تایپ سیگنچر ِ ‏‎foldr‎‏ به نظر خیلی مفهوم نیاد، پس اول با تایپِ ‏‎map‎‏ مقایسه‌ش می‌کنیم. فقط دقت کنین که تایپِ ‏‎foldr‎‏ از 7.10 GHC و جدیدتر، تغییر کرد:

-- و قدیمی‌تر GHC 7.8
foldr :: (a -> b -> b) -> b -> [a] -> b

-- و جدیدتر GHC 7.10
foldr :: Foldable t
      => (a -> b -> b)
      -> b
      -> t a
      -> b

کنار هم بذاریم:

foldr :: Foldable t =>
         (a -> b -> b) -> b -> t  a -> b
foldr :: (a -> b -> b) -> b -> [] a -> b

فعلاً فقط همین قدر توضیح میدیم که 7.10 GHC توابعِ فولد رو انتزاعی‌تر کرد، و بجای اینکه فقط با لیست‌ها کار کنن، الان با هر نوع‌داده‌ای که قابلیتِ فولد شدن رو داشته باشه کار می‌کنن. همیشه هم میشه به نسخه‌ی معیّن‌تَرش رسید (اما برعکس‌ش ممکن نیست):

Prelude> :{
Prelude| let listFoldr :: => (a -> b -> b)
Prelude|                  -> b
Prelude|                  -> [] a
Prelude|                  -> b
Prelude|     listFoldr = foldr
Prelude| :}
Prelude> :t listFoldr
listFoldr :: (a -> b -> b) -> b -> [a] -> b

حالا به این توازی بینِ ‏‎map‎‏ و ‏‎foldr‎‏ دقت کنین:

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

-- چطور کار می‌کرد؟ map یادتون هست
map   :: (a -> b) -> [a] -> [b]
map (+1) 1  :       2  :       3  : []

    (+1) 1  :  (+1) 2  :  (+1) 3  : []

-- با همون لیست بالا
foldr (+) 0 (1  :   2  :   3  :  [])

             1  +  (2  +  (3  +   0))

تابعِ ‏‎map‎‏ یک تابع رو به تک‌تکِ اعضای لیست اعمال می‌کنه و یه لیست برمی‌گردونه. اما فولد، داده‌سازهای cons رو با تابع جایگزین می‌کنه و لیست رو حذف می‌کنه.