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

Question

Из того, что я понимаю о сгибах в Haskell, 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 (-) 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 2

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

---

В случае списков, 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 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

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