Функция fold_left действительно рекурсивна, однако она отлично работает как для маленьких, так и для больших списков.В небольших списках нет смысла использовать fold_right вместо fold_left.Функция fold_left всегда * быстрее fold_right, и вы слышали, что вы слышали не о fold_left против fold_right, а о хвостовой рекурсивной версии fold_right противнерекурсивная версия fold_right.Но прежде всего позвольте мне выделить разницу между правым и левым сгибами .
Левый сгиб принимает список элементов
a b c d ... z
и функцию fи выдает значение
(f (f (f (f a b) c) d) ... z)
Проще понять, если представить, что f - некоторый оператор, например, сложение, и использовать инфиксную нотацию a + b вместо префиксной нотации.(add a b), поэтому левый сгиб уменьшит последовательность до суммы следующим образом
((((a + b) + c) + d) + ... + z)
Итак, мы видим, что левый сгиб связывает круглые скобки слева.Это единственное отличие от правой складки, которая фактически связывает круглые скобки с правой, поэтому, если мы возьмем ту же последовательность и применим ту же функцию к ней, используя правильную складку, у нас будет следующее вычисление
(a + (b + ... (x + (y + z))))
В случае операции сложения результат будет одинаковым как для левой, так и для правой складки.Тем не менее, правильная реализация будет менее эффективной.Причина этого в том, что для левой складки мы можем вычислить результат, как только получим два элемента, например, a+b, где для правой складки нам нужно вычислить результат сложения n-1 элементов., а затем добавьте первый элемент, например, a + (b + ... + (y + z)).Следовательно, правый сгиб должен где-то хранить промежуточные результаты.Самый простой способ - использовать стек, например, a::rest -> a + (fold_right (+) rest 0)), где значение a помещается в стек, затем выполняется вычисление (fold_right (+) rest 0)), и когда оно будет готово, мы наконец можем добавить a исумма всех других элементов.В конце концов, он будет выдвигать все значения a, b, ... x, пока мы наконец не доберемся до y и z, которые мы можем суммировать, а затем развернуть стек вызовов.
Проблема со стеком в том, что он обычно ограничен, в отличие от кучи памяти, которая может расти без границ.Это на самом деле не относится к математике или дизайну компьютерных языков, это то, как современные операционные системы запускают программы, они дают им пространство стека фиксированного размера и размер несвязанной кучи.И как только у программы заканчивается размер стека, операционная система завершает его без возможности восстановления.Это очень плохо, и по возможности его следует избегать.
Поэтому люди предложили более безопасную реализацию fold_right, как левый сгиб обратного списка.Очевидно, что этот компромисс приводит к более медленной реализации, поскольку нам необходимо по существу создать обратную копию списка ввода, и только после этого пройти его с помощью функции fold_left.В результате мы дважды пройдемся по списку и создадим мусор, что еще больше снизит производительность нашего кода.Поэтому у нас есть компромисс между быстрой, но небезопасной реализацией, предоставляемой стандартной библиотекой, и надежной и безопасной, но медленной реализацией, предоставляемой некоторыми другими библиотеками.
Подводя итог, можно сказать, что fold_left всегда быстрее, чем fold_right, и всегда хвост рекурсивен.Стандартная реализация OCaml fold_right не является хвостовой рекурсивной, что быстрее, чем хвостовая рекурсивная реализация fold_right функций, предоставляемых некоторыми другими библиотеками.Однако это связано с ценой, вы не должны применять fold_right к большим спискам.В целом это означает, что в OCaml вы должны предпочесть fold_left в качестве основного инструмента для обработки списков.