۱۰ - ۵فولد از چپ

به خاطر طرز کار لیست‌ها، فولدها باید اول از روی کلِ ستون ِ لیست، از ابتدا تا انتها پیش برن. در فولد ِ چپ و راست، جهتِ پیمایش ِ ستون یکسانه، ولی در ‏‎foldl‎‏، فرایندِ فولد کردن شرکت‌پذیری از چپ داره و در خلافِ جهتِ ‏‎foldr‎‏ انجام میشه.

در زیر یه تعریف ساده از ‏‎‎‏foldl رو آوردیم. باز هم مثل ‏‎foldr‎‏، تایپ‌ها ممکنه فرق داشته باشن:

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acc []     = z
foldl f acc (x:xs) = f x (foldr f acc xs)

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

-- با لیست زیر
foldl (+) 0 (1  :   2  :   3  :  [])

-- اینطوری شرکت داده میشه foldl
           ((0  +   1) +   2) +   3

برای دیدنِ شرکت‌پذیری ِ ‏‎foldl‎‏، می‌تونیم از همون کَلَکی که برای ‏‎foldr‎‏ زَدیم استفاده کنیم:

Prelude> let f x y = concat ["(",x,"+",y,")"]

Prelude> foldl f "0" (map show [1..5])
"(((((0+1)+2)+3)+4)+5)"

می‌بینیم که ‏‎foldl‎‏ رَوندِ ساده‌سازی‌ش رو با اضافه کردن سَر ِ لیست به مقدارِ ‏‎acc‎‏ (م. خلاصه‌ی accumulator به معنای مخزن یا جمع‌کننده) شروع می‌کنه، ولی ‏‎foldr‎‏ از آخرین المانِ لیست شروع می‌کرد.

از اسکن‌ها هم میشه برای دیدنِ نحوه‌ی محاسبه در فولدها استفاده کرد. اسکن‌ها شبیه فولدها اند، با این تفاوت که در نهایت یه لیست شامل مقادیر حاصل در هر مرحله‌ی فولد رو برمی‌گردونن. اگه ‏‎scanr‎‏ و ‏‎scanl‎‏ رو با فولدهاشون مقایسه کنیم:

Prelude> foldr (+) 0 [1..5]
15
Prelude> scanr (+) 0 [1..5]
[15,14,12,9,5,0]

Prelude> foldl (+) 0 [1..5]
15
Prelude> scanl (+) 0 [1..5]
[0,1,3,6,10,15]

چنین رابطه‌ای بین‌شون دیده میشه:

last (scanl f z xs) = foldl f z xs
head (scanr f z xs) = foldr f z xs

فولد کردن و شرکت‌پذیری

اینجا به چندتا از تأثیراتِ شرکت‌پذیری ِ ‏‎foldl‎‏ نگاهِ دقیق‌تری میندازیم. همونطور که گفتیم، هر دو فولدها ستون رو در یک جهت پیمایش می‌کنن. چیزی که بین‌شون فرق داره، شرکت‌پذیری ِ محاسبه‌ست.

نگرشِ اساسی که به محاسبات در هسکل میشه داشت، دیدنِ اونها به چشمِ جایگزینی ‌ِه. وقتی یه لیست رو با ‏‎f‎‏ و مقدار اولیه‌ی ‏‎z‎‏ از راست فولد می‌کنیم، میشه گفت داریم داده‌سازهای cons رو با تابع فولدینگ، و داده‌ساز ِ "لیست خالی" رو با مقدار شروعیِ ‏‎z‎‏ جایگزین می‌کنیم:

[1..3] = 1 : 2 : 3 : []

foldr f z [1, 2, 3]
1 `f` (foldr z [2, 3])
1 `f` (2 `f` (foldr z [3]))
1 `f` (2 `f` (3 `f` (foldr z [])))
1 `f` (2 `f` (3 `f` z))

از طرف دیگه، به خاطرِ محاسبه‌ی تنبل اختیارِ تعیینِ ترتیبِ محاسبه به توابع داده میشه. در نتیجه اون پرانتزها واقعی‌اند. در مثال بالا ‏‎3 `f` z‎‏ اول محاسبه میشه، چون داخلی‌ترین پرانتزه. فولدها لیست رو از بیرون به داخل پیمایش می‌کنن، ولی خودِ فولد کردن در فولد از راست، از انتهای لیست شروع میشه.

دیدن تأثیرِ چنین چیزی رو با توابعِ شرکت‌پذیر نمیشه دید، ولی درک این موضوع مهمه، پس ما هم چندتا مثالِ دیگه رو بررسی می‌کنیم. اول بریم سراغِ تابعِ توان:

Prelude> foldr (^) 2 [1..3]
1
Prelude> foldl (^) 2 [1..3]
64

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

-- اگه می‌خواین با کتاب پیش بیاین،
-- REPL رو کاغذ بنویسین، نه تو
foldr (^) 2 [1..3]
(1 ^ (2 ^ (3 ^ 2))) 
(1 ^ (2 ^ 9)) 
1 ^ 512
1

با این مقایسه کنین:

foldl (^) 2 [1..3]
((2 ^ 1) ^ 2) ^ 3
(2 ^ 2) ^ 3
4 ^ 3
64

در مثال بعدی، با فولد کردن ِ یه لیست به یه لیست جدید، تأثیرِ شرکت‌پذیری رو نشون میدیم:

Prelude> foldr (:) [] [1..3]
[1,2,3]
Prelude> foldl (flip (:)) [] [1..3]
[3,2,1]

برای ‏‎foldl‎‏ باید از ‏‎flip‎‏ استفاده کنیم. ببینیم چرا.

مثل فولد از راست، فولد از چپ هم نمی‌تونه جادو کنه و یِهو بِره آخر لیست؛ باید از اولِ لیست شروع کنه. با این حال، پرانتزها نحوه‌ی محاسبه‌ی کُدمون رو تعیین می‌کنن. علاوه بر شرکت‌پذیری، تایپِ آرگومان تابعِ فولدینگ هم تغییر می‌کنه:

foldr :: (a -> b -> b) -> b -> [a] -> b
--       [1]  [2]  [3]
foldl :: (b -> a -> b) -> b -> [a] -> b
--       [4]  [5]  [6]

از تایپِ ‏‎(:)‎‏ میشه دید که انتظار داره آرگومانِ اول‌ِش مقدار، و آرگومانِ دوم‌ش یه لیست باشه:

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

پس مقدار ورودی، به اولِ لیست پیش‌افزوده میشه (یا پشتِ لیست cons میشه).

در مثال‌های زیر تیلدا (م. یا مدَّک) "معادل یا برابر است با" معنی میده. با داده‌ساز ِ cons بجای ‏‎f‎‏ و لیستِ خالی بجای ‏‎z‎‏، اگه از راست فولد کنیم:

-- foldr f z [1,2,3]
-- f ~ (:); z ~ []
-- میده. True اجرا کنین، REPL اگه در
(==) (foldr (:) [] (1 : 2 : 3 : []))
     (1 : (2 : (3 : [])))

اینجا تایپ سیگنچرها با هم جور اند (تابعِ cons با تابع فولدینگ برای ‏‎foldr‎‏). حتی همون لیستِ ورودی رو جواب میده چون داریم داده‌سازهای cons رو با داده‌سازهای cons، و لیست خالی رو با لیست خالی جایگزین می‌کنیم. ولی شرکت‌پذیری از راست برای یکسان بودن‌شون واجب‌ِه.

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

foldl f z [1, 2, 3]
-- f ~ (:); z ~ []
-- (((z `f` 1) `f` 2) `f` 3)
((([] : 1) : 2) : 3)

الان ‏‎z‎‏ یه لیستِ خالی شده و ‏‎f‎‏ هم cons، که آرگومان‌هاش برعکس‌اند و کار نمی‌کنه. تابعِ ‏‎flip‎‏ جای دو تا آرگومان اولِ تابعِ ورودی‌ش رو عوض می‌کنه و در نتیجه همون تابع رو با آرگومان‌های جابجا شده برمی‌گردونه، که اینجا به کار میاد:

foldl f z [1, 2, 3]
-- f ~ (flip (:)); z ~ []
-- (((z `f` 1) `f` 2) `f` 3)
f = flip (:)
((([] `f` 1) `f` 2) `f` 3)
 (([1] `f` 2) `f` 3)
  ([2, 1] `f` 3)
   [3, 2, 1]

با اینکه تایپ‌ها رو درست کردیم، ذاتِ شرکت‌پذیری از چپ در ‏‎foldl‎‏ منجر به یه جوابِ متفاوتی نسبت به ‏‎foldr‎‏ شد.

برای سری بعدی مثال‌ها، از تابعی به اسمِ ‏‎const‎‏ که دو آرگومان می‌گیره و همیشه آرگومان اول‌ِش رو برمی‌گردونه استفاده می‌کنیم. وقتی ‏‎const‎‏ رو روی یه لیست فولد می‌کنیم، دو آرگومان‌ش مقادیرِ لیست و مقدارِ ‏‎acc‎‏ میشن – اینکه کدوم یکی آرگومانِ اول‌ِش باشه بستگی به نوعِ فولدی داره که استفاده می‌کنیم. با مثال زیر شروع می‌کنیم:

Prelude> foldr const 0 [1..5]
(const 1 _)
1

از اونجا که ‏‎const‎‏ آرگومانِ دوم‌ش رو اجبار نمی‌کنه، مابقیِ ‏‎‎‏فولد هم اصلاً محاسبه نشد. خط تیره مابقیِ فولد (که حساب نشد) رو نشون میده. حالا ببینیم اگه آرگومان‌ها رو جابجا کنیم چی میشه:

Prelude> foldr (flip const) 0 [1..5]
0

جواب صفر شد چون مقدارِ ‏‎acc‎‏ صفر بود.

حالا از همون تابع با ‏‎foldl‎‏ مثال میزنیم. یه کم فکر کنین تا متوجهِ مراحلِ محاسبه تا رسیدن به این جواب‌ها بشین:

Prelude> foldl (flip const) 0 [1..5]
5
Prelude> foldl const 0 [1..5]
0

این تأثیرِ شرکت‌پذیری از چپ ِه. پیمایش ِ ستون برای فولد ِ چپ و راست یکسانه – به خاطر نحوه‌ی تعریف شدنِ لیست‌ها، باید یکسان باشن. بسته به تابع فولدینگ، فولد ِ چپ ممکنه جواب متفاوتی از فولد ِ راست بده.

تمرین‌ها: درک فولدها

flip (*) 1 [1..5]

foldl (flip (*)) 1 [1..5] 

foldl (*) 1 [1..5]

پیش‌روی ِ بی‌قیدوشرط از روی ستون

در فولد از چپ، مراحل بعدیِ فولد به عنوان آرگومانِ اولِ تابع فولدینگ داده میشه، و این یکی از تفاوت‌های مهم بینِ ‏‎foldr‎‏ و ‏‎foldl‎‏ ِه. برخلافِ ‏‎foldr‎‏، در ‏‎foldl‎‏ تابعِ فولدینگ هیچ مداخله‌ای در پیش‌روی روی ستون نمی‌کنه، به عبارت دیگه، پیش‌روی‌ش روی ستون بی‌قیدوشرط ِه. به کار بردنِ تابعی که محاسبه‌ی هیچ کدوم از آرگومان‌هاش رو اجبار نمی‌کنه تأثیری نداره. دوباره ‏‎const‎‏ رو نگاه کنیم:

Prelude> const 1 undefined
1
Prelude> (flip const) 1 undefined
*** Exception: Prelude.undefined
Prelude> (flip const) undefined 1
1

حالا با این مقایسه کنین:

Prelude> let xs = [1..5] ++ undefined
Prelude> foldr const 0 xs
1
Prelude> foldr (flip const) 0 xs
*** Exception: Prelude.undefined

Prelude> foldl const 0 xs
*** Exception: Prelude.undefined
Prelude> foldl (flip const) 0 xs
*** Exception: Prelude.undefined

با اینکه ‏‎foldl‎‏ بی‌قیدوشرط ستون رو محاسبه می‌کنه، اما هنوز میشه روی محاسبه‌ی مقادیرِ داخلِ لیست اختیار داشت. مثالِ زیر به خاطر تهی بودنِ بخشی از ستون خطا میده چون ‏‎foldl‎‏ تمامِ ستون رو محاسبه می‌کنه:

Prelude> let xs = [1..5] ++ undefined
Prelude> foldl (\_ _ -> 5) 0 xs
*** Exception: Prelude.undefined

اما در این مثال، تهی یکی از مقادیره و موردی نداره:

Prelude> let xs = [1..5] ++ [undefined]
Prelude> foldl (\_ _ -> 5) 0 xs
5

این خصوصیت نشون میده که عموماً ‏‎foldl‎‏ برای لیست‌هایی که بینهایت هستن (یا ممکنه باشن)، مناسب نیست. از طرف دیگه، این محاسبه‌ی بی‌قیدوشرط ِ ستون، و در کنارش نااکید بودن، یعنی استفاده از ‏‎foldl‎‏ برای لیست‌های طولانی هم معمولاً خوب نیست، چون اجبار برای محاسبه‌ی ستون، عملکرد رو هم تضعیف می‌کنه. ‏‎foldl‎‏ قبل از اینکه شروع به محاسبه‌ی هر سلول کنه، باید کلِ ستون رو محاسبه کنه. همین میشه که با پیمایش از روی ستون، تعداد زیادی مقادیرِ محاسبه‌نشده رو تلنبار می‌کنه.

در اکثر موارد که به فولد از چپ احتیاج دارین، باید از ‏‎foldl'‎‏ استفاده کنین. این تابع که "فولد-اِل-پرایم" خونده میشه، مثلِ ‏‎foldl‎‏ کار می‌کنه، با این تفاوت که اکید ِه. یعنی با پیمایش ِ ستون، بجای تلنبار کردنِ بیانیه‌های محاسبه نشده به ازای هر المانِ لیست، مقادیرِ داخل سلول‌‌های cons رو هم اجبار می‌کنه. این محاسبه‌ی اکید، تأثیر منفیِ فولد کردن ِ لیست‌های طولانی از چپ رو کم می‌کنه.