我是OCaml的新手，我从其他帖子中看到fold_left中的List是尾递归并且在较大的列表上工作得更好，而fold_right不是尾递归。我的问题是为什么fold_left只能在更大的列表上运行得更好，它是如何实现的，这使得它在较小的列表上不能更好地工作。
尾递归允许避免大量内存分配。该优化将与列表的长度成正比。
在一个小清单上，会有一个收益，但在你开始使用大清单之前它不太可能引人注意。
根据经验，你应该使用fold_left，除非你正在处理一个小列表，而fold_right版本更符合你想要编写的内容。
fold_left函数确实是尾递归的，但它在小型和大型列表上都能正常工作。在小名单上使用fold_right而不是fold_left没有任何好处。 fold_left函数总是比fold_right更快，你听到的谣言不是关于fold_left和fold_right，而是关于fold_right的尾递归版本与fold_right的非尾递归版本。但首先让我强调right and left folds之间的区别。
左侧折叠采用元素列表
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快，并且总是尾递归。 fold_right的标准OCaml实现不是尾递归，这比其他一些库提供的fold_right函数的尾递归实现更快。但是，这需要付出代价，您不应将fold_right应用于大型列表。一般来说，这意味着在OCaml中你必须更喜欢fold_left作为处理列表的主要工具。