Haskell-foldl и foldr?

Ответ 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', потому что он строгий и останавливает создание длинного списка промежуточных результатов. (Подробнее об этой теме в ответах на этот вопрос.)