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

155

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

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

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

Дж Купер
источник

Ответы:

174

Рекурсия для того, 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 он оценивается как f y1 thunk, поэтому он возвращает False, однако в foldl f не может знать ни один из его параметров. В Haskell, независимо от того, является ли это хвостовой рекурсией или нет, оба могут вызвать переполнение thunks, т.е. thunk слишком большой. Foldl 'может уменьшить гром сразу по ходу исполнения.
Сойер
25
Чтобы избежать путаницы, обратите внимание, что в скобках не указан фактический порядок оценки. Поскольку Haskell ленив, внешние выражения будут оцениваться первыми.
Лии
Великий ответ. Я хотел бы добавить, что если вы хотите фолд, который может остановить часть пути в списке, вы должны использовать foldr; если я не ошибаюсь, левые складки не могут быть остановлены. (Вы намекаете на это, когда говорите: «Если вы знаете ... вы ... пройдете весь список»). Кроме того, опечатка «использование только значения» должна быть изменена на «использование только значения». Т.е. убрать слово «вкл». (Stackoverflow не позволил бы мне внести изменение в 2 символа!).
Lqueryvg
@Lqueryvg два способа остановить левые сгибы: 1. закодировать с правым сгибом (см. fodlWhile); 2. преобразовать его в левое сканирование ( scanl) и остановить его с помощью last . takeWhile pили аналогичным. Ну, и 3. использовать mapAccumL. :)
Уилл Несс
1
@Desty, потому что он производит новую часть своего общего результата на каждом шаге - в отличие от этого foldl, который собирает свой общий результат и производит его только после того, как вся работа завершена и больше нет шагов для выполнения. Так, например foldl (flip (:)) [] [1..3] == [3,2,1], так scanl (flip(:)) [] [1..] = [[],[1],[2,1],[3,2,1],...]... IOW, foldl f z xs = last (scanl f z xs)и бесконечные списки не имеют последнего элемента (который, в приведенном выше примере, сам по себе будет бесконечным списком, от INF до 1).
Уилл Несс
57

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

Правосторонняя визуализация

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

Визуализация влево

Контекст: Свернуть на вики Haskell

Грег Бэкон
источник
33

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

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

Конрад Рудольф
источник
Их семантика отличается лишь тривиальным образом, что бессмысленно на практике: порядок аргументов используемой функции. Поэтому с точки зрения интерфейса они все еще считаются взаимозаменяемыми. Похоже, реальная разница заключается только в оптимизации / реализации.
Evi1M4chine
2
@ Evi1M4chine Ни одно из различий не является тривиальным. Наоборот, они существенны (и, да, значимы на практике). На самом деле, если бы я написал этот ответ сегодня, он бы еще больше подчеркнул эту разницу.
Конрад Рудольф
23

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

mattiast
источник
18

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

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

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

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

Axman6
источник
1
Большое исключение - если переданная функция foldlничего не делает, кроме применения конструкторов к одному или нескольким аргументам.
dfeuer
Существует ли общая модель того, когда foldlна самом деле лучший выбор? (Как бесконечные списки, когда foldrнеправильный выбор, с точки зрения оптимизации.?)
Evi1M4chine
@ Evi1M4chine не уверен, что вы подразумеваете под foldrнеправильным выбором для бесконечных списков. На самом деле, вы не должны использовать foldlили foldl'для бесконечных списков. Смотрите вики на Haskell о переполнении стека
KevinOrr
14

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

newacct
источник
2
Этот комментарий полезен, но я был бы признателен за источники.
titaniumdecoy
Обычный Лисп reduceне ленив, так что foldl'многие соображения здесь не применимы.
MicroVirus
Я думаю, что вы имеете в виду foldl', поскольку они строгие языки, нет? Иначе, не будет ли это означать, что все эти версии вызывают переполнение стека, как это foldlпроисходит?
Evi1M4chine
6

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

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

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

Jonas
источник
Их тип такой же, только что переключился, что не имеет значения. Их интерфейс и результаты одинаковы, за исключением сложной проблемы P / NP (читай: бесконечные списки). ;) Насколько я могу судить, оптимизация за счет реализации - единственное отличие на практике.
Evi1M4chine
@ Evi1M4chine Это неверно, посмотрите на этот пример: foldl subtract 0 [1, 2, 3, 4]оценивает -10, а foldr subtract 0 [1, 2, 3, 4]оценивает -2. foldlна самом деле 0 - 1 - 2 - 3 - 4пока foldrесть 4 - 3 - 2 - 1 - 0.
krapht
@krapht, foldr (-) 0 [1, 2, 3, 4]есть -2и foldl (-) 0 [1, 2, 3, 4]есть -10. С другой стороны, subtractэто обратное от того, что вы можете ожидать ( subtract 10 14есть 4), так foldr subtract 0 [1, 2, 3, 4]есть -10и foldl subtract 0 [1, 2, 3, 4]есть 2(положительно).
pianoJames