Foldl является хвостовой рекурсией, так почему же Foldr работает быстрее, чем Fold?
Я хотел проверить фолд против фолд. Из того, что я видел, вы должны использовать 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 побеждает foldl. Разве это не должно быть ясным случаем, когда победит фолдл?
7 ответов
Добро пожаловать в мир ленивых оценок.
Когда вы думаете об этом с точки зрения строгой оценки, 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' в вашем тесте, но это на самом деле заставило его работать медленнее.)
РЕДАКТИРОВАТЬ: После повторного рассмотрения этой проблемы, я думаю, что все текущие объяснения несколько недостаточно, поэтому я написал более длинное объяснение.
Разница в том, как 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' не меняет способ создания промежуточного списка. Глава списка остается недоступной до тех пор, пока не завершится сложение, поэтому результат будет медленнее, чем при foldr,
Я использую следующее правило, чтобы определить лучший выбор fold
- Для складок, которые являются сокращением, используйте
foldl'(например, это будет единственный / последний обход) - В противном случае используйте
foldr, - Не использовать
foldl,
В большинстве случаев foldr является лучшей функцией сгиба, потому что направление обхода оптимально для ленивых вычислений списков. Это также единственный способный обрабатывать бесконечные списки. Особая строгость foldl' может сделать это быстрее в некоторых случаях, но это зависит от того, как вы будете использовать эту структуру и насколько она ленива.
Я не думаю, что кто-то на самом деле сказал настоящий ответ на этот вопрос, пока я что-то упустил (что вполне может быть правдой и приветствуется с отрицательными голосами).
Я думаю, что самым большим отличием в этом случае является то, что foldr строит список так:
[0] ++ ([1] ++ ([2] ++ (... ++ [1000000])))
В то время как foldl строит список так:
((([0] ++ [1]) ++ [2]) ++...) ++ [999888]) ++ [999999]) ++ [1000000]
Разница в тонких, но обратите внимание, что в foldr версия ++ всегда имеет только один элемент списка в качестве левого аргумента. С foldl в версии до 999999 элементов ++левый аргумент (в среднем около 500000), но только один элемент в правом аргументе.
Тем не мение, ++ занимает время, пропорциональное размеру левого аргумента, так как он должен просмотреть весь список левых аргументов до конца, а затем переназначить этот последний элемент первому элементу правого аргумента (в лучшем случае, возможно, ему действительно нужно выполнить копия). Правильный список аргументов неизменен, поэтому не имеет значения, насколько он велик.
Вот почему foldl Версия намного медленнее. По моему мнению, это не имеет ничего общего с ленью.
Проблема в том, что оптимизация хвостовой рекурсии - это оптимизация памяти, а не оптимизация времени выполнения!
Оптимизация хвостовой рекурсии избавляет от необходимости запоминать значения для каждого рекурсивного вызова.
Таким образом, 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 эквивалентны только при определенных условиях, описанных здесь
(Извините за мой плохой английский)
Для [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]
Каждый из этих промежуточных списков не может быть повторно использован, потому что, если вы измените конец списка, вы изменили любые другие значения, которые на него указывают. Таким образом, вы создаете кучу дополнительных списков, которые требуют времени для создания памяти. Таким образом, в этом случае вы тратите гораздо больше времени на распределение и заполнение этих списков, которые являются промежуточными значениями.
Поскольку вы просто создаете копию списка, процесс запускается быстрее, поскольку он начинается с расширения полного списка, а затем просто перемещает указатель из задней части списка в начало.
Ни foldl ни foldr оптимизирован для хвоста. Это только foldl',
Но в вашем случае, используя ++ с foldl' не очень хорошая идея, потому что последовательная оценка ++ будет вызывать пересечение растущего аккумулятора снова и снова.
Что ж, позвольте мне переписать ваши функции так, чтобы различие было очевидным -
a :: a -> [a] -> [a]
a = (:)
b :: [b] -> b -> [b]
b = flip (:)
Вы видите, что b сложнее, чем a. Если вы хотите быть точным a для расчета значения требуется один шаг уменьшения, но b нужно два. Это делает разницу во времени, которую вы измеряете, во втором примере вдвое больше сокращений.
// edit: Но сложность времени та же самая, поэтому я бы не стал сильно беспокоиться об этом.