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

Question

Я хотел протестировать foldl vs foldr. Из того, что я видел, вы должны использовать foldl over foldr, когда когда-либо сможете, из-за оптимизации рекурсии хвоста.

Это имеет смысл. Тем не менее, после выполнения этого теста я запутался:

foldr (требуется 0.057s при использовании команды времени):

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

main = putStrLn(show (sum (foldr a [] [0.. 100000]))) 

foldl (требуется 0.089s при использовании команды времени):

b::[b] -> b -> [b] 
b xs = (++ xs). (\y->[y]) 

main = putStrLn(show (sum (foldl b [] [0.. 100000]))) 

Понятно, что этот пример тривиален, но я смущен тем, почему foldr избивает foldl. Разве это не должно быть ясным случаем, когда побеждает склад?

Answer 1

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

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

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

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

Это не было бы слишком хорошо, если 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' в тесте, но он на самом деле сделал это работать медленнее.)

Answer 2

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

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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

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

Answer 5

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

Разница заключается в том, как 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 ', поэтому результат все равно будет медленнее, чем с foldr.

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

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

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

Answer 6

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

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

Итак, складной на самом деле «хороший», а складной «плохой».

Например, с учетом определения 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) 

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

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 нет. foldr запоминает одно целое для каждого вызова и выполняет добавление в каждом вызове.

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

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

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

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

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

Answer 7

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

Я считаю, что самая отличается в данном случае является то, что foldr строит список, как это:

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

в то время как foldl строит список, как это:

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

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

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

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