我应该选择哪一种？

Question

我记得当我给我的教授看一些代码时，他不假思索地说

这并不重要，但值得注意的是，在SML/NJ中，fold*比fold*'更高效，因此在可能的情况下，您应该更喜欢使用它而不是fold*。

我忘了fold*是foldr还是foldl。我知道这是那些在实践中可能不会有太大影响的微观优化之一，但我想习惯于在我有选择的时候使用更高效的那个。

哪个是哪个？我猜想这是SML/NJ特有的，MLton将足够聪明地优化这两个机器代码，但是其他编译器的答案是很好的。

Answer 1

更喜欢将给定输入转换为预期输出的输入。

如果两者都产生相同的输出，例如使用和，如果处理list，则从左侧折叠将更有效，因为折叠可以以head元素开始，而从右侧折叠将首先需要遍历列表以在计算第一个中间结果之前找到最后一个元素。

对于数组和类似的随机访问数据结构，可能不会有太大的差别。

编译器的优化总是选择左和右的优点，这将要求编译器确定左和右在所有可能的输入上是等价的。由于foldl和foldr将一个函数作为参数，所以这是一个很高的要求。

Answer 2

foldl是尾递归的，而foldr不是.尽管您可以以尾递归的方式执行foldr，方法是反转列表(这是尾递归的)，然后执行foldl。

这将是唯一重要的，如果你是折叠在庞大的名单。

Answer 3

我将在这里保留公认的答案，但我有机会与我的教授交谈，而他的回答实际上正好相反，因为我忘记了我的问题的一部分。这一守则正在形成一份清单，他说：

如果可能的话，更喜欢foldr而不是foldl，因为在折叠期间通过添加元素来构建列表的情况下，它会在最后保存一个reverse。

与之类似，对于一个微不足道的例子：

- val ls = [1, 2, 3];
val ls = [1,2,3] : int list
- val acc = (fn (x, xs) => x::xs);
val acc = fn : 'a * 'a list -> 'a list
- foldl acc [] ls;
val it = [3,2,1] : int list
- foldr acc [] ls;
val it = [1,2,3] : int list

反向的O(n)保存可能比回答这个问题时提到的foldl和foldr之间的其他差异更重要。