Haskell - foldl vs foldr
функції foldl та foldr називають згорткою
згортка - функція, яку ми застосовуємо до функції2, списку зі значеннями та акумулятора,
у свою чергу, функція2 бере значення зі списку та акумулятор, проводить розрахунки і повертає новий акумулятор,
далі функція2 застосовується до наступного значення зі списку з новим акумулятором,
і так поки у списку залишаються значення
при застосуванні foldl та foldr розгортаються наступним чином
foldl f2 acc [a1, a2, a3, a4] =
f2 (f2 (f2 (f2 acc a1) a2) a3) a4
foldr f2 acc [a1, a2, a3, a4] =
f2 a1 (f2 a2 (f2 a3 (f2 a4 acc)))
напишемо дві функції щоб зробити тест foldl та foldr
test_foldr :: [Integer] -> IO [Integer]
test_foldr v = foldr (\x a -> print x >> a) (return []) v
test_foldl :: [Integer] -> IO [Integer]
test_foldl v = foldl (\a x -> print x >> a) (return []) v
застосуємо спочатку до невеличкого списку
ghci> test_foldr [5,4..0]
5
4
3
2
1
0
[]
ghci> test_foldl [5,4..0]
0
1
2
3
4
5
[]
тут ми відмінностей не помітили
що буде при застосуванні до великого списку?
test_foldr [10000000000000,9999999999999..0]
10000000000000
9999999999999
9999999999998
...
тут все ок :)
а от при застосуванні test_foldl навіть до меншого(коротшого) списку можна втрапити в халепу -
адже при ліво-асоціативному обчисленні для того щоб вивести результат розрахунків з першим елементом -
потрібно перед цим провести розрахунки з усіма іншими елементами списку!
відповідно, якщо вистачить оперативної памяті -- нам доведеться почекати закінчення цих розрахунків,
якщо ж оперативки не вистачить - отримаємо stack overflow...
тому замість
test_foldl [10000000,9999999..0]
краще викликати
test_foldr [0..10000000]
також test_foldr можна застосовувати до нескінченних списків, на відміну від test_foldl :)