Понимание сгибов в Haskell

Question

Из того, что я понимаю о складках в Хаскеле, foldl (-) 0 [1..5] дает результат -15 вычисляя 0-1-2-3-4-5, а также foldr (-) 0 [1..5] дает результат -5 вычисляя 5-4-3-2-1-0, Почему тогда оба foldl (++) "" ["a", "b", "c"] а также foldr (++) "" ["a", "b", "c"] дать результат "abc"и результат foldr вместо этого "cba"?

Есть ли что-то, что мне не хватает в понимании различий между foldl а также foldr?

Answer 1

Я думаю, что эта часть из документов проясняет:

---

В случае списков, foldr, когда применяется к бинарному оператору, начальное значение (обычно правая идентификация оператора) и список, сокращает список с помощью бинарного оператора справа налево:

foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)

,,,

В случае списков, foldl, при применении к бинарному оператору, начальное значение (обычно левый идентификатор оператора) и список сокращает список с помощью бинарного оператора слева направо:

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

---

Если вы посмотрите на пример разбивки, конкатенация foldr эквивалентно:

"a" ++ ("b" ++ ("c" ++ ""))

И для foldl, это будет эквивалентно:

(("" ++ "a") ++ "b") ++ "c"

Для конкатенации строк это одно и то же.

---

Однако для вычитания

1 - (2 - (3 - 0))

Дает другой результат, чем:

((0 - 1) - 2) - 3

Answer 2

На самом деле foldr (-) 0 [1..5] равняется 3, потому что это:

(1 - (2 - (3 - (4 - (5 - 0))))

Ответ на этот вопрос в виде foldr функция:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

Как мы видим, (a -> b -> b) функция имеет итерированный элемент в качестве первого аргумента и накопитель в качестве второго. Вот почему с foldr (++) "" ["a", "b", "c"] у нас есть:

("a" ++ ("b" ++ ("c" ++ "")))

Answer 3

Символически воспринимается как "перевод" сгиба, 0-1-2-3-4-5 само по себе плохо определено. Порядок операций должен быть указан.

На самом деле, независимо от оператора, порядок

foldl (-) 0 [1..5] = ((((0 - 1) - 2) - 3) - 4) - 5    -- = -15

foldr (-) 0 [1..5] = 1 - (2 - (3 - (4 - (5 - 0))))    -- = 3

Для (++) хотя оба порядка приводят к одному и тому же результату, когда "" используется вместо 0,

Answer 4

Я обнаружил, что это самый поучительный способ понять разницу (поскольку идея «левоассоциативности» для меня нова): -- комментарии отражают :doc foldr и :doc foldl

*Main> foldr (-) 2 [1,4,8] -- foldr fz [a,b,c] == a (b (cz))

3

*Main> 1 - (4 - ( 8 - 2)) -- правая ассоциативная папка

3

*Main> ((2 - 1) - 4) -8 -- свернуть левый ассоциативный

-11

*Main> foldl (-) 2 [1,4,8] -- foldl fz [a,b,c] == ((za) b) fс

-11