List.fold_left实现与List.fold_right实现

Question

我是OCaml的新手，我从其他文章中看到，List中的fold_left是尾递归的，在较大的列表上工作得更好，而fold_right不是尾递归。我的问题是，为什么fold_left只在较大的列表上工作得更好，它是如何实现的，使它不能在较小的列表上工作得更好。

Answer 1

尾递归可以避免大量的内存分配。这种优化将直接与列表的长度成正比。

在一个小的列表上，会有一些收获，但在你开始使用大的列表之前，它不太可能被注意到。

根据经验，您应该使用fold_left，除非您正在处理一个很小的列表，并且fold_right版本更符合您要编写的内容。

Answer 2

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)

因此，我们可以看到左边的文件夹与左边的括号相关联。这是它与right fold的唯一区别，right fold实际上将括号关联到右侧，因此，如果我们将使用相同的序列，并使用right fold对其应用相同的函数，我们将进行以下计算

(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作为处理列表的主要工具。