Foldl хвост рекурсивный, так как же foldr работает быстрее, чем foldl?

Ответ 1

Добро пожаловать в мир ленивой оценки.

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

Однако ленивая оценка превращает таблицы. Возьмем, например, определение функции отображения:

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

Это не было бы слишком хорошо, если бы Haskell использовал строгую оценку, так как сначала он должен был вычислить хвост, а затем добавить элемент (для всех элементов в списке). Кажется, что единственный способ сделать это эффективно - создать элементы в обратном направлении.

Однако, благодаря ленивой оценке Haskell, эта функция карты действительно эффективна. Списки в Haskell можно рассматривать как генераторы, и эта функция карты генерирует свой первый элемент, применяя f к первому элементу входного списка. Когда ему нужен второй элемент, он снова делает то же самое (без использования дополнительного пространства).

Оказывается, что map можно описать в терминах foldr:

map f xs = foldr (\x ys -> f x : ys) [] xs

Трудно сказать, глядя на него, но ленивая оценка, потому что foldr может сразу дать свой первый аргумент f:

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

Поскольку f, определяемый map, может возвращать первый элемент списка результатов, используя только первый параметр, сложение может работать лениво в постоянном пространстве.

Теперь ленивая оценка откусывает. Например, попробуйте запустить сумму [1..1000000]. Это приводит к переполнению стека. Почему это должно быть? Он должен просто оценить слева направо, правильно?

Посмотрим, как это оценивает Haskell:

foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

sum = foldl (+) 0

sum [1..1000000] = foldl (+) 0 [1..1000000]
                 = foldl (+) ((+) 0 1) [2..1000000]
                 = foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
                 = foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
                   ...
                 = (+) ((+) ((+) (...) 999999) 1000000)

Haskell слишком ленив, чтобы выполнять дополнения по мере их появления. Вместо этого он заканчивается башней необоснованных громов, которые должны быть вынуждены получить номер. Во время этой оценки происходит переполнение стека, так как оно должно глубоко заново оценивать все трюки.

К счастью, в Data.List есть специальная функция, называемая foldl', которая работает строго. foldl' (+) 0 [1..1000000] не будет переполнять переполнение. (Примечание: я попытался заменить foldl на foldl' в вашем тесте, но он фактически запустил его медленнее.)

Ответ 2

РЕДАКТИРОВАТЬ: снова посмотрев на эту проблему, я думаю, что все текущие объяснения несколько недостаточны, поэтому я написал более подробное объяснение.

Разница заключается в том, как foldl и foldr применяют свою функцию сокращения. Рассматривая случай foldr, мы можем развернуть его как

foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...

Этот список обрабатывается sum, который потребляет его следующим образом:

sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000])     -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000])  -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...

Я не учитывал детали конкатенации списка, но это то, как происходит сокращение. Важная часть состоит в том, что все обрабатывается, чтобы минимизировать переходы по спискам. foldr перемещается только один раз, конкатенации не требуют непрерывных обходов списка, а sum, наконец, потребляет список за один проход. Критически, глава списка доступен с foldr сразу до sum, поэтому sum может начать работать немедленно, а значения могут быть gc'd по мере их создания. С каркасами слияния, такими как vector, даже промежуточные списки, скорее всего, будут сработаны.

Контрастируйте это с помощью функции foldl:

b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...

Обратите внимание, что теперь глава списка недоступна, пока foldl не закончит. Это означает, что весь список должен быть сконструирован в памяти до того, как sum может начать работать. Это намного менее эффективно. Запуск двух версий с +RTS -s показывает жалкую производительность сборки мусора из версии foldl.

Это также случай, когда foldl' не поможет. Добавленная строгость foldl' не изменяет способ создания промежуточного списка. Глава списка остается недоступной до тех пор, пока команда foldl 'не завершится, поэтому результат будет медленнее, чем с foldr.

Я использую следующее правило для определения наилучшего выбора fold

• Для сгибов, которые являются сокращением, используйте foldl' (например, это будет единственный/окончательный обход)
• В противном случае используйте foldr.
• Не используйте foldl.

В большинстве случаев foldr - лучшая функция сгиба, потому что направление обхода оптимально для ленивой оценки списков. Это также единственный способ обработки бесконечных списков. Дополнительная строгость foldl' может ускорить работу в некоторых случаях, но это зависит от того, как вы будете использовать эту структуру и насколько она ленива.

Ответ 3

Я не думаю, что кто-то действительно сказал реальный ответ на этот, пока я не упустил что-то (что вполне может быть правдой и приветствуется с downvotes).

Я думаю, что самым большим в этом случае является то, что foldr строит список следующим образом:

[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))

В то время как foldl строит список следующим образом:

((([0] ++ [1]) ++ [2]) ++...) ++ [999888]) ++ [999999]) ++ [1000000]

Разница в тонкой, но заметьте, что в версии foldr ++ всегда есть только один элемент списка в качестве его левого аргумента. С версией foldl в ++ левом аргументе (в среднем около 500000) есть до 999999 элементов, но только один элемент в правильном аргументе.

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

Вот почему версия foldl намного медленнее. По моему мнению, это не имеет никакого отношения к лени.

Ответ 4

Проблема заключается в том, что оптимизация хвостовой рекурсии - оптимизация памяти, а не оптимизация времени выполнения!

Оптимизация регенерации хвоста позволяет избежать необходимости запоминать значения для каждого рекурсивного вызова.

Итак, foldl на самом деле "хороший", а foldr "плохой".

Например, учитывая определения foldr и foldl:

foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs

foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)

То, как оценивается выражение "foldl (+) 0 [1,2,3]":

foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6

Обратите внимание, что foldl не запоминает значения 0, 1, 2..., но передает все выражение ((0 + 1) +2) +3) как аргумент лениво и не оценивает его до тех пор, пока последняя оценка foldl, где она достигает базового случая и возвращает значение, прошедшее как второй параметр (z), который еще не оценен.

С другой стороны, как работает foldr:

foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6

Важное различие здесь заключается в том, что, когда foldl оценивает все выражение в последнем вызове, избегая необходимости возвращаться, чтобы достичь запоминаемых значений, foldr no. foldr запоминает одно целое для каждого вызова и выполняет добавление в каждом вызове.

Важно помнить, что foldr и foldl не всегда эквивалентны. Например, попробуйте вычислить эти выражения в объятиях:

foldr (&&) True (False:(repeat True))

foldl (&&) True (False:(repeat True))

foldr и foldl эквивалентны только при определенных условиях, описанных здесь

(извините за мой плохой английский)

Ответ 5

Для a список [0.. 100000] необходимо развернуть сразу, так что foldr может начинаться с последнего элемента. Затем, когда он складывает вещи вместе, промежуточные результаты

[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list

Поскольку никто не может изменить значение этого списка (Haskell - это чистый функциональный язык), компилятор может повторно использовать это значение. Промежуточные значения, такие как [99999, 100000], могут быть просто указателями в расширенный список [0.. 100000] вместо отдельных списков.

Для b просмотрите промежуточные значения:

[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]

Каждый из этих промежуточных списков нельзя использовать повторно, потому что если вы измените конец списка, вы измените любые другие значения, указывающие на него. Таким образом, вы создаете кучу дополнительных списков, которые требуют времени для сборки в памяти. Таким образом, в этом случае вы тратите намного больше времени на распределение и заполнение этих списков, которые являются промежуточными значениями.

Поскольку вы просто делаете копию списка, выполняется быстрее, потому что он начинается с расширения полного списка, а затем просто перемещает указатель со спины списка на передний план.

Ответ 6

Ни foldl, ни foldr не оптимизирован хвостом. Это только foldl'.

Но в вашем случае использование ++ с foldl' не является хорошей идеей, потому что последовательная оценка ++ приведет к повторному обходу растущего аккумулятора.

Ответ 7

Хорошо, позвольте мне переписать ваши функции таким образом, чтобы разница была очевидной -

a :: a -> [a] -> [a]
a = (:)

b :: [b] -> b -> [b]
b = flip (:)

Вы видите, что b более сложный, чем a. Если вы хотите быть точным, a требуется один шаг перехода для вычисления значения, но b требуется два. Это делает разницу во времени, которую вы измеряете, во втором примере в два раза должно быть выполнено сокращение.

//edit: Но временная сложность такая же, поэтому я бы не стал ее сильно беспокоиться.