۱۰ - ۷فولد کردن و محاسبه
شرکتپذیری نقطهی تمایزِ 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]