۱۰ - ۴فولد از راست

به ‏‎foldr‎‏ فولد از راست میگیم چون فولد شرکت‌پذیری از راست داره؛ یا به کلام دیگه، از راست پرانتزگذاری میشه. این رو در تعریفِ ‏‎foldr‎‏ هم میشه دید:

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

حتماً شباهتهای بین این و بقیه‌ی تابع‌های بازگشتی که بالاتر دیدیم براتون واضحه. یکی از آرگومان‌های تابعِ ‏‎f‎‏ (تابعِ فولدینگ)، "مابقیِ فولد" (یا ‏‎foldr f z xs‎‏) هست. ‏‎z‎‏ میشه صفرِ فولد؛ هم یه مقدار پشتیبان برای وقتی که لیستِ ورودی به ‏‎foldr‎‏ خالی باشه، هم یه آرگومانِ دومی که اجازه میده فولد رو شروع کنیم. معمولاً از مقدار همانی ِ تابعِ فولدینگ برای این صفر استفاده میشه، مثل عدد صفر برای ‏‎(+)‎‏، و ۱ برای ‏‎(*)‎‏.

‏‎foldr‎‏ چطور محاسبه می‌کنه

برای اینکه بتونیم راحت‌تر توضیح بدیم، یه کم تعریفی که بالاتر از ‏‎foldr‎‏ نوشتیم رو تغییر میدیم. البته این تغییرات تأثیری روی مفهومِ تعریف نمیذارن:

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr f z xs =
  case xs of
    []     -> z
    (x:xs) -> f x (foldr f z xs)

اینجا میشه دید که فولد از راست، شرکت‌پذیری از راست داره. این هم مشابهِ مثالِ ‏‎sum‎‏ که بالاتر نوشتیم ساده میشه:

foldr (+) 0 [1, 2, 3]

اولین قدم برای ساده کردنِ این فولد، جایگذاریِ آرگومانِ ورودی بجای ‏‎xs‎‏ در بیانیه‌ی case ِه:

foldr (+) 0 [1, 2, 3]
  case [1, 2, 3] of
    ...

با کدوم یکی از حالت‌ها انطباق داره؟

foldr (+) 0 [1, 2, 3]
  case [1, 2, 3] of
    []     -> z
    (x:xs) -> f x (foldr f z xs) -- <-- این یکی

خب، در اون شاخه‌ی case، متغیرهای ‏‎f‎‏، ‏‎x‎‏، ‏‎xs‎‏، و ‏‎z‎‏ به چه مقادیری مقیّد شدن؟

foldr (+) 0 [1, 2, 3]
  case [1, 2, 3] of
    []           -> 0
    (1 : [2, 3]) ->
      (+) 1 (foldr (+) 0 [2, 3])

از اونجا که ‏‎(+)‎‏ در هر دو آرگومان‌ش اَکید ِه، ما هم ‏‎(foldr (+) 0 [2,3])‎‏ رو باز می‌کنیم؛ یعنی مرحله‌ی بعدیِ این محاسبه‌ی بازگشتی رو اجبار می‌کنیم. البته ممکنه تابع فولدینگ تابعی باشه که مابقیِ فولد رو مکرراً اجبار نکنه. برای مثال ‏‎const‎‏ چنین تابعی‌ه؛ همیشه اولین آرگومان‌ش رو برمی‌گردونه (یه کم جلوتر بیشتر توضیح میدیم). پس اینجا، خوداتکایی ِ بعدی میشه ‏‎(foldr (+) 0 [2,3])‎‏:

foldr (+) 0 [2, 3]
  case [2, 3] of
    []        -> 0 -- باز هم این منطبق نشد
    (2 : [3]) -> (+) 2 (foldr (+) 0 [3])

به طور ضمنی، تابعِ ‏‎(+) 1‎‏ از بیرون به کل کُدِ بالا اعمال شده. تابعِ ‏‎(+)‎‏ به هر دو آرگومان‌ش اکید بودن ِ بی‌قیدوشرط داره، پس باز هم خوداتکایی ِ تابعِ ‏‎foldr‎‏ رو ادامه میدیم. می‌بینید که یکی‌دَر‌میون داریم تابعِ ‏‎f‎‏ و ‏‎foldr‎‏ رو صدا میزنیم. این رفت و برگشت، بیشترِ اختیار رو به تابعِ فولدینگ (تابعی که باهاش فولد می‌کنیم) میده. یه تابع فولدینگ مثل ‏‎const‎‏، با محاسبه نکردنِ آرگومان دوم‌ش (که همون "مابقیِ فولد" ِه)، تعیین کننده‌ی کاهش میزان کارِ محاسباتی میشه.

مشابهِ بالا، تابعِ ‏‎(+) 1 ((+) 2 ...)‎‏ به صورت ضمنی دورِ کُد زیر رو پوشونده:

foldr (+) 0 [3]
  case [3] of
    []       -> 0 -- باز هم این منطبق نشد
    (3 : []) -> (+) 3 (foldr (+) 0 [])

یک بار دیگه، برای بار آخر، ‏‎foldr‎‏ رو صدا می‌زنیم. باز هم دورِ کُد زیر به صورت ضمنی با ‏‎(+) 1 ((+) 2 ((+) 3...))‎‏ پوشونده شده. حالا می‌رسیم به فرمان پایه:

foldr (+) 0 []
  case [] of
    [] -> 0 -- بالاخره این یکی منطبق شد
    -- اون یکی حالت دیگه مهم نیست

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

foldr (+) 0 [1, 2, 3]

به این فرم بازنویسی کرده:

(+) 1 ((+) 2 ((+) 3 0))

اگه بخوایم تمیزتر بنویسیم، بدون اینکه شیوه‌ی محاسبه‌ش رو تغییر بدیم، اینجوری میشه:

1 + (2 + (3 + 0))

مثل حساب، داخلی‌ترین پرانتز رو اول حساب می‌کنیم:

1 + (2 + (3 + 0))
1 + (2 + 3)
1 + 5
6

حالا محاسبه تموم شد، با جواب ۶.

برای دیدنِ نحوه‌ی شرکت‌پذیری در فولد، می‌تونیم از یه کَلَکی که توسطِ چندتا از کاربران در جامعه‌ی IRC ِ هسکل معروف شد هم استفاده کنیم.^*

xs = map show [1..5]
y = foldr (\x y -> concat
    ["(",x,"+",y,")"]) "0" xs

با صدا زدنِ ‏‎y‎‏ در REPL، نحوه‌ی محاسبه‌ی ‏‎foldr‎‏ رو می‌بینیم:

Prelude> y
"(1+(2+(3+(4+(5+0)))))"

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

در ‏‎foldr‎‏، "مابقیِ فولد" میشه آرگومان دومِ تابعی که باهاش فولد می‌کنیم:

foldr f z (x:xs) = f x (foldr f z xs)
--                     ^------------^
--                       مابقی فولد

به خاطرِ این محاسبه‌ی دو مرحله‌ای و نااکید، اگه ‏‎f‎‏ آرگومانِ دوم‌ش (مابقی فولد) رو محاسبه نکنه، بقیه‌ی ستون هم اجبار نمیشه. در نتیجه ‏‎foldr‎‏ علاوه بر قابلیت اجتناب از محاسبه‌ی بعضی یا همه‌ی مقادیرِ لیست، می‌تونه از محاسبه‌ی بخشی یا کلِ ستون ِ لیست هم اجتناب کنه! به همین دلیل ‏‎foldr‎‏ برای لیست‌هایی که به احتمال بینهایت‌اند هم قابل استفاده‌ست. برای نمونه، مثال‌های زیر رو مقایسه کنین (یادتون باشه که ‏‎(+)‎‏ بی‌قیدوشرط، کلِ ستون و همه‌ی مقادیر رو حساب می‌کنه):

Prelude> foldr (+) [1..5]
15

‏‎foldr‎‏ به همراه جمع، برای لیستِ بینهایت قابل استفاده نیست، اما اگه بجای جمع از توابعی که در هر دو آرگومان‌شون اکید نیستن استفاده کنیم، برای رسیدن به جواب نیاز به محاسبه‌ی همه‌ی مقادیر نداریم و در نتیجه ‏‎foldr‎‏ هم قابل اعمال میشه. برای مثال، تابع ‏‎myAny‎‏ به محض دیدنِ یک مقدارِ ‏‎True‎‏ جوابِ ‏‎True‎‏ برمی‌گردونه:

myAny :: (a -> Bool) -> [a] -> Bool
myAny f xs =
  foldr (\x b -> f x || b) False xs

این مثال، با اینکه لیست‌ش بینهایت‌ه کار می‌کنه:

Prelude> myAny even [1..]
True

اما این یکی محاسبه‌ش تموم نمیشه، چون همیشه فرد ِه:

Prelude> myAny even (repeat 1)

به چنین محاسبه‌ی بی‌پایانی تهی یا ‏‎undefined‎‏ هم میگیم. با فولد ِ لیست‌های بینهایت تضمینی برای رسیدن به جواب نیست، حتی اگه از ‏‎foldr‎‏ استفاده کنین؛ معمولاً بستگی به داده ِ ورودی و تابع فولدینگ داره. چند مثال با تهی ِ ساده‌تر رو ببینیم:

Prelude> let u = undefined

-- میدیم undefined اینجا یه مقدارِ
Prelude> foldr (+) 0 [1, 2, 3, 4, u]
*** Exception: Prelude.undefined

Prelude> let xs = take 4 [1, 2, 3, 4, u]
Prelude> foldr (+) 0 xs
10

-- بخشی از ستون‌ه undefined اینجا
Prelude> let xs = [1, 2, 3, 4] ++ u
Prelude> foldr (+) 0 xs
*** Exception: Preldue.undefined
Prelude> let xs = take 4 ([1,2,3,4] ++ u)
Prelude> foldr (+) 0 xs
10

وقتی فقط ۴ المان اول رو می‌گیریم، فرایندِ فولدینگ ِ بازگشتی رو بعد از ۴ المانِ اول متوقف می‌کنیم و در نتیجه تابعِ جمع به تهی نمی‌خوره، چه یکی از مقادیر باشه، چه بخشی از ستون ِ لیست.

تابعِ ‏‎length‎‏ رفتارِ متفاوتی داره؛ مقادیر رو محاسبه نمی‌کنه، ولی ستون رو بی‌قیدوشرط حساب می‌کنه:

Prelude> length [1, 2, 3, 4, undefined]
5
Prelude> length ([1, 2, 3, 4] ++ undefined)
*** Exception: Prelude.undefined

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

Prelude> let xs = [1, 2, 3, 4] ++ undefined
Prelude> length (take 4 xs)
4

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

Prelude> let xs = [1, 2] ++ undefined
Prelude> length $ take 2 $ take 4 xs
2

مهم نیست که ‏‎take 4‎‏ به تهی می‌خورد! به خاطرِ ‏‎take 2‎‏ ِ قبل‌ش اصلاً اجبار نشد.

حالا که طرز کار آرگومان دوم به تابعِ فولدینگ ِ ‏‎foldr‎‏ رو دیدیم، نگاهی به آرگومانِ اول‌ش میندازیم:

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

آرگومانِ اول (‏‎[1]‎‏) از یه تطبیق الگو، که به طور پیش‌فرض اکید ِه بدست میاد – تابعِ ‏‎f‎‏ فقط در صورتی به ‏‎x‎‏ اعمال میشه که یه مقدارِ ‏‎x‎‏ وجود داشته باشه و یه لیستِ خالی نباشه. این به این معنی‌ه که تابعِ ‏‎foldr‎‏ باید یه سلول cons ِ اولیه رو اجبار کنه تا بتونه فرق بین دو حالتِ ‏‎[]‎‏ و ‏‎(x:xs)‎‏ رو تشخیص بده. در نتیجه سلول cons ِ اول نمی‌تونه تهی یا تعریف‌نشده باشه.

پس ‏‎foldr‎‏ بخشِ اولِ ستون رو محاسبه می‌کنه. سعی می‌کنیم با چندتا مثالِ غیرمعمول این رو نشون بدیم. اینجا یه تابعِ بی‌نام و نسبتاً مسخره تعریف کردیم که همه‌ی آرگومان‌هاش رو نادیده می‌گیره و مقدارِ ۹۰۰۱ رو برمی‌گردونه. چنین تابعی هیچ کدوم از آرگومان‌هاش رو مجبور به محاسبه نمی‌کنه، یعنی موردی نداره اگه بخشی از ستون ِ لیست، یا یکی از مقادیرِ داخلِ لیست تهی باشه:

Prelude> foldr (\_ _ -> 9001) 0 [1..5]
9001

Prelude> let xs = [1, 2, 3, undefined]
Prelude> foldr (\_ _ -> 9001) 0 xs
9001

Prelude> let xs = [1, 2, 3] ++ undefined
Prelude> foldr (\_ _ -> 9001) 0 xs
9001

تا وقتی بخشِ اولِ ستون تهی نباشه، همه چیز خوبه:

Prelude> foldr (\_ _ -> 9001) 0 undefined
*** Exception: Prelude.undefined

Prelude> let xs = [1, undefined] 
Prelude> foldr (\_ _ -> 9001) 0 xs
9001

Prelude> let xs = [undefined, undefined] 
Prelude> foldr (\_ _ -> 9001) 0 xs
9001

دوتا مثالِ آخر کار کردن چون اولین سلول cons ِشون تهی نبود – اون مقادیرِ تعریف‌نشده داخل سلول‌‌های cons اند، نه خودِ ستون. به کلام دیگه، سلول‌‌های cons حاوی مقادیر تهی اند، ولی خودشون تهی نیستن. بعداً با اکید بودن و نااکید بودن بیشتر آزمایش می‌کنیم تا تأثیرشون رو روی نحوه‌ی محاسبه در برنامه‌هامون ببینیم.

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

-- :یادآوری
-- const :: a -> b -> a
-- const x _ = x

Prelude> const 1 2
1 
Prelude> const 2 1
2
Prelude> foldr const 0 [1..5]
1
Prelude> foldr const 0 [1, undefined]
1
Prelude> foldr const 0 ([1, 2] ++ undefined)
1
Preldue> foldr const 0 [undefined, 2]
*** Exception: Prelude.undefined

حالا که طریقه‌ی محاسبه‌ی ‏‎foldr‎‏ رو دیدیم، قبل از ادامه به نوشتن و استفاده از فولدها، نگاهی به ‏‎foldl‎‏ میندازیم.