Foldl является хвостовой рекурсией, так почему же Foldr работает быстрее, чем Fold?

Question

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

Это имеет смысл. Однако после запуска этого теста я запутался:

foldr (занимает 0,057 с при использовании команды времени):

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

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

foldl (занимает 0,089 с при использовании команды времени):

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

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

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

Answer 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 слишком ленив для выполнения дополнений. Вместо этого это заканчивается башней неоцененных громов, которые должны быть вынуждены получить число. Переполнение стека происходит во время этой оценки, так как он должен глубоко повторяться для оценки всех thunks.

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

Answer 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 может начать работать немедленно, и значения могут быть сгенерированы после их генерирования.С фреймворками, такими как 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' может сделать ее быстрее в некоторых случаях, но это зависит от того, как вы будете использовать эту структуру и насколько она ленивая.

Answer 3

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

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

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

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

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

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

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

Answer 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 эквивалентны только при определенных условиях, описанных здесь

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

Answer 5

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

[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]

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

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

Answer 6

Ни foldl, ни foldr не оптимизированы для хвоста. Это всего лишь foldl'.

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

Answer 7

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

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

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

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

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