Последствия foldr vs foldl (или foldl ')

Во-первых, Real World Haskell, который я читаю, говорит, что никогда не используйте foldl и вместо этого используйте foldl'. Поэтому я верю.

Но я не понимаю, когда использовать foldr vs. foldl'. Хотя я вижу структуру того, как они работают по-разному, передо мной, я слишком глуп, чтобы понять, когда "что лучше". Думаю, мне кажется, что это не имеет особого значения, потому что они оба дают один и тот же ответ (не так ли?). На самом деле, мой предыдущий опыт работы с этой конструкцией - от Ruby inject и Clojure reduce, которые, похоже, не имеют "левых" и "правильных" версий. (Боковой вопрос: какую версию они используют?)

Любое понимание, которое может помочь умному, подобному мне мнению, будет очень оценено!

Ответ 1

Рекурсия для foldr f x ys, где ys = [y1,y2,...,yk] выглядит как

f y1 (f y2 (... (f yk x) ...))

тогда как рекурсия для foldl f x ys выглядит как

f (... (f (f x y1) y2) ...) yk

Важным отличием здесь является то, что если результат f x y можно вычислить, используя только значение x, тогда foldr не нужно исследовать весь список. Например

foldr (&&) False (repeat False)

возвращает False, тогда как

foldl (&&) False (repeat False)

никогда не заканчивается. (Примечание: repeat False создает бесконечный список, где каждый элемент False.)

С другой стороны, foldl' является хвостом рекурсивным и строгим. Если вы знаете, что вам придется пересекать весь список независимо от того, что (например, суммируя числа в списке), то foldl' больше пространства (и, вероятно, времени), чем foldr.

Ответ 2

foldr выглядит следующим образом:

foldl выглядит следующим образом:

Контекст: Fold в вики Haskell

Ответ 3

Их семантика отличается тем, что вы не можете просто обменять foldl и foldr. Один складывает элементы слева, а другой справа. Таким образом, оператор применяется в другом порядке. Это имеет значение для всех неассоциативных операций, таких как вычитание.

Haskell.org имеет интересную статью по теме.

Ответ 4

В скором времени foldr лучше, когда функция аккумулятора ленив по второму аргументу. Подробнее о Haskell wiki Переполнение стека (каламбур).

Ответ 5

Причина foldl' предпочтительнее foldl, поскольку 99% всех применений состоит в том, что она может работать в постоянном пространстве для большинства целей.

Возьмем функцию sum = foldl['] (+) 0. Когда используется foldl', сумма немедленно вычисляется, поэтому применение sum к бесконечному списку будет выполняться вечно и, скорее всего, в постоянном пространстве (если вы используете такие вещи, как Int s, Double s, Float s. Integer будет использовать больше, чем постоянное пространство, если число станет больше, чем maxBound :: Int).

С foldl создается thunk (как рецепт того, как получить ответ, который может быть оценен позже, вместо сохранения ответа). Эти thunks могут занимать много места, и в этом случае гораздо лучше оценить выражение, чем хранить thunk (приводя к переполнению стека и hellip, и приводя вас к & hellip; ох, неважно)

Надеюсь, что это поможет.

Ответ 6

Кстати, Ruby inject и Clojure reduce являются foldl (или foldl1, в зависимости от используемой вами версии). Обычно, когда в языке есть только одна форма, это левая справка, включая Python reduce, Perl List::Util::reduce, С++ accumulate, С# Aggregate, Smalltalk inject:into:, PHP array_reduce, Mathematica Fold и т.д. Common Lisp reduce по умолчанию используется влево, но есть опция для правильной складки.

Ответ 7

Как отмечают Konrad, их семантика отличается. Они даже не имеют один и тот же тип:

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci>

Например, оператор добавления списка (++) может быть реализован с помощью foldr как

(++) = flip (foldr (:))

(++) = flip (foldl (:))

даст вам ошибку типа.