Во-первых, Real World Haskell , который я читаю, говорит никогда не использовать, foldl
а вместо этого использовать foldl'
. Поэтому я верю в это.
Но я не знаю, когда использовать foldr
против foldl'
. Хотя я вижу структуру их работы по-разному, но я слишком глуп, чтобы понять, когда «что лучше». Я думаю, мне кажется, что не должно иметь значения, какой из них используется, поскольку они оба дают один и тот же ответ (не так ли?). Фактически, мой предыдущий опыт работы с этой конструкцией был взят из Ruby inject
и Clojure reduce
, которые, похоже, не имеют «левой» и «правой» версий. (Дополнительный вопрос: какую версию они используют?)
Любое понимание, которое может помочь таким умным людям, как я, будет высоко ценится!
источник
fodlWhile
); 2. преобразовать его в левое сканирование (scanl
) и остановить его с помощьюlast . takeWhile p
или аналогичным. Ну, и 3. использоватьmapAccumL
. :)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).foldr
выглядит так:foldl
выглядит так:Контекст: Свернуть на вики Haskell
источник
Их семантика различаются , так что вы не можете просто поменять местами
foldl
иfoldr
. Один складывает элементы слева, другой справа. Таким образом, оператор применяется в другом порядке. Это важно для всех неассоциативных операций, таких как вычитание.На Haskell.org есть интересная статья на эту тему.
источник
Короче,
foldr
лучше, когда функция-накопитель ленива в своем втором аргументе. Читайте больше в переполнении стека на вики Haskell (каламбур).источник
Причина,
foldl'
по которойfoldl
для 99% всех применений предпочтительнее, заключается в том, что он может работать в постоянном пространстве для большинства применений.Возьми функцию
sum = foldl['] (+) 0
. Когдаfoldl'
используется, сумма вычисляется немедленно, поэтому применениеsum
к бесконечному списку будет выполняться вечно и, скорее всего, в постоянном пространстве (если вы используете такие вещи, какInt
s,Double
s,Float
s.Integer
S будет использовать больше, чем постоянное пространство, если номер становится больше чемmaxBound :: Int
).С
foldl
помощью thunk создается (как рецепт того, как получить ответ, который можно оценить позже, а не хранить ответ). Эти блоки могут занимать много места, и в этом случае гораздо лучше оценить выражение, чем сохранить блок (что приводит к переполнению стека… и ведет к… о, неважно)Надеюсь, это поможет.
источник
foldl
ничего не делает, кроме применения конструкторов к одному или нескольким аргументам.foldl
на самом деле лучший выбор? (Как бесконечные списки, когдаfoldr
неправильный выбор, с точки зрения оптимизации.?)foldr
неправильным выбором для бесконечных списков. На самом деле, вы не должны использоватьfoldl
илиfoldl'
для бесконечных списков. Смотрите вики на Haskell о переполнении стекаКстати, Ruby
inject
и Clojurereduce
естьfoldl
(илиfoldl1
, в зависимости от того, какую версию вы используете). Обычно, когда в языке есть только одна форма, это левое свертывание, включая Pythonreduce
, PerlList::Util::reduce
, C ++accumulate
, C #Aggregate
, Smalltalkinject:into:
, PHParray_reduce
, Mathematica иFold
т. Д. Поreduce
умолчанию Common Lisp по умолчанию использует левое сворачивание, но есть опция для правого сворачивания.источник
reduce
не ленив, так чтоfoldl'
многие соображения здесь не применимы.foldl'
, поскольку они строгие языки, нет? Иначе, не будет ли это означать, что все эти версии вызывают переполнение стека, как этоfoldl
происходит?Как указывает Конрад , их семантика различна. У них даже нет того же типа:
Например, оператор добавления списка (++) может быть реализован
foldr
какпока
выдаст вам ошибку типа.
источник
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
.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
(положительно).