۱۰ - ۷فولد کردن و محاسبه

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

Prelude> let rcf = foldr (:) []
Prelude> let xs = [1, 2, 3] ++ undefined
Prelude> take 3 $ rcf xs
[1,2,3]
Prelude> let lcf = foldl (flip (:)) []
Prelude> take 3 $ lcf xs
*** Exception: Prelude.undefined

برگردیم به مثالِ ‏‎const‎‏ و یه کم دقیق‌تر نگاه‌ش کنیم:

foldr const 0 [1..5]

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

Prelude> foldr const 0 ([1] ++ undefined)
1

Prelude> head ([1] ++ undefined)
1
Prelude> tail ([1] ++ undefined)
*** Exception: Prelude.undefined

مشابهِ همین با ‏‎foldl‎‏:

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

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

رابطه‌ی ‏‎foldr‎‏ و ‏‎foldl‎‏ طوریه که:

foldr f z xs =
  foldl (flip f) z (reverse xs)

اما فقط برای لیست‌های متناهی! فرض کنین:

Prelude> let xs = repeat 0 ++ [1,2,3]
Prelude> foldr const 0 xs
0
Prelude> let xs' = repeat 1 ++ [1,2,3]
Prelude> let rxs = reverse xs'
Prelude> foldrl (flip const) 0 rxs
^CInterrupted.
-- ^^ یا تهی bottom

اگه تابع فولدینگ ِ ‏‎f‎‏ رو جابجا و لیستِ ‏‎xs‎‏ رو معکوس کنیم، ‏‎foldr‎‏ و ‏‎foldl‎‏ یک جواب میدن:

Prelude> let xs = [1..5]
Prelude> foldr (:) [] xs
[1,2,3,4,5]
Prelude> foldl (flip (:)) [] xs
[5,4,3,2,1]
Prelude> foldl (flip (:)) [] (reverse xs)
[1,2,3,4,5]
Prelude> reverse $ foldl (flip (:)) [] xs
[1,2,3,4,5]