ublog

haskell -- foldl vs foldr

programming [47]haskell [4]

функції 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 :)


далі буде :)