Последствия фолд против фолд (или фолдл)
Во-первых, Real World Haskell, который я читаю, говорит никогда не использовать foldl и вместо этого использовать foldl', Поэтому я верю в это.
Но я не знаю, когда использовать foldr против foldl', Хотя я вижу структуру их работы, изложенную по-разному передо мной, я слишком глуп, чтобы понять, когда "что лучше". Я думаю, мне кажется, что не должно иметь значения, какой из них используется, поскольку они оба дают один и тот же ответ (не так ли?). На самом деле, мой предыдущий опыт с этой конструкцией взят из Ruby's inject и Clojure's reduce, которые, кажется, не имеют "левой" и "правой" версии. (Дополнительный вопрос: какую версию они используют?)
Любое понимание, которое может помочь таким умным людям, как я, будет высоко ценится!
7 ответов
Рекурсия для 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,
Их семантика отличается, поэтому вы не можете просто поменяться foldl а также foldr, Один складывает элементы слева, другой справа. Таким образом, оператор применяется в другом порядке. Это важно для всех неассоциативных операций, таких как вычитание.
http://haskell.org/ есть интересная статья на эту тему.
Вскоре, foldr лучше, когда функция-накопитель ленива по второму аргументу. Читайте больше на переполнении стека на вики Haskell (каламбур).
Причина foldl' предпочтительнее foldl для 99% всех применений это то, что он может работать в постоянном пространстве для большинства применений.
Взять на себя функцию sum = foldl['] (+) 0, когда foldl' используется, сумма сразу рассчитывается, поэтому применение sum к бесконечному списку просто будет работать вечно, и, скорее всего, в постоянном пространстве (если вы используете такие вещи, как Ints, Doubles, Floats. Integers будет использовать больше, чем постоянное пространство, если число становится больше, чем maxBound :: Int).
С foldlсоздается раздел (как рецепт того, как получить ответ, который можно оценить позже, а не хранить ответ). Эти блоки могут занимать много места, и в этом случае гораздо лучше оценить выражение, чем сохранить блок (что приводит к переполнению стека… и ведет к… о, неважно)
Надеюсь, это поможет.
Кстати, Руби inject и Clojure's reduce являются foldl (или же foldl1в зависимости от того, какую версию вы используете). Обычно, когда в языке есть только одна форма, это левый сгиб, включая Python reducePerl's List::Util::reduce, C++ accumulateC# AggregateSmalltalk's inject:into:PHP array_reduceМатематика Foldи т. д. Обычный Лисп reduce по умолчанию левый сгиб, но есть вариант с правым сгибом.
Как указывает Конрад, их семантика различна. У них даже нет того же типа:
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 (:))
даст вам ошибку типа.