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

EDIT: при повторном рассмотрении этой проблемы я думаю, что все текущие объяснения несколько недостаточны, поэтому я написал более длинное объяснение.

разница в том, как 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, даже промежуточные списки, скорее всего, будут расплавлены.

сравните это с :

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.

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

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

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

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

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

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

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

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

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

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

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

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

, тогда как foldl строит список следующим образом:

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

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

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

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

на тег [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]

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

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

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

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

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

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

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

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

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