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

Сравните это с функцией 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 .

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

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

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

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

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

Для 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]

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

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

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

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

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

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

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