Последствия фолд против фолд (или фолд)

Question

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

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

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

Answer 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.

Answer 2

foldr выглядит так:

foldl выглядит так:

Контекст: Сгиб на вики Haskell

Answer 3

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

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

Answer 4

Короче, foldr лучше, когда функция накопителя ленива по второму аргументу. Читайте больше на переполнении стека на вики Haskell (каламбур предназначен).

Answer 5

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

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

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

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

Answer 6

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

Answer 7

Как указывает Конрад , их семантика различна. Они даже не имеют тот же тип:

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 (:))

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