Хаскель - фолдл и фолд?

Question

Разница между foldl а также foldr только направление петли? Я думал, что есть разница в том, что они сделали, а не только в направлении?

Answer 1

Есть разница, если ваша функция не ассоциативна (то есть имеет значение, каким образом вы заключаете выражения в скобки), например,
foldr (-) 0 [1..10] = -5 но foldl (-) 0 [1..10] = -55,
В небольшом масштабе это потому, что 10-(20-(30)) не то же самое, что ((10)-20)-30,

Тогда как (+) является ассоциативным (не имеет значения, в каком порядке вы добавляете подвыражения),
foldr (+) 0 [1..10] = 55 а также foldl (+) 0 [1..10] = 55, (++) это еще одна ассоциативная операция, потому что xs ++ (ys ++ zs) дает тот же ответ, что и (xs ++ ys) ++ zs (хотя первый быстрее - не используйте foldl (++),

Некоторые функции работают только в одном направлении:
foldr (:) :: [a] -> [a] -> [a] но foldl (:) ерунда

Посмотрите на диаграммы Кейла Гиббарда (из статьи в Википедии); ты можешь видеть f вызов с действительно разными парами данных:

Другое отличие состоит в том, что, поскольку он соответствует структуре списка, foldr часто более эффективен для ленивых вычислений, поэтому может использоваться с бесконечным списком до тех пор, пока f не является строгим во втором аргументе (например, (:) или же (++)). foldl только изредка лучший выбор. Если вы используете foldl обычно стоит использовать foldl' потому что это строго и мешает вам составить длинный список промежуточных результатов. (Подробнее об этой теме в ответах на этот вопрос.)