使用Scheme的reverse函数非常容易，例如在使用(cons new-obj my-list)而不是(append my-list (list new-obj))以相反顺序创建列表之后。
然而，我想知道部分的效率有多高。如果Scheme列表是一个单链表(正如我所假设的(，这意味着至少遍历整个列表一次才能到达最后一个元素，不是吗？这将需要reverse以某种方式创建反向链路？
在双链接列表中，OTOH只需从列表的末尾遍历到列表的开头，这将更有效。
我的问题是：如果我遇到这样的情况，一个程序生成一个列表(按相反的顺序(，并在某个时刻处理整个列表，那么以一种可以按相反顺序处理列表的方式来实现这种处理值得吗？还是先简单地使用reverse没有惩罚？
这是针对Guile Scheme和Guile 1.8的(如果有区别的话(。
反转需要O(n(时间来创建n-长反转列表，因此也需要O(n">空间。您只需遍历原始列表一次即可将其反转。
如果不再使用原始列表，则可能会对其进行垃圾收集(何时？成为问题(，并回收其内存，以节省总体理论O(1(空间成本；但垃圾收集有其自身的成本。
所以，测试一下，如果你的列表很长，并且你看到很多垃圾收集正在进行，那么就按照你的建议去做。它将或多或少地使您的时间和空间需求减半(在代码库的那个部分(。
但是，如果列表的建立和反转占用了你总时间和空间的0.0001%，那么减半就不会有太大的改善。
顺便说一下，在单独链接的列表中没有反向链接。反转只是通过重复cons来在遍历原始单元格时构建新的cons单元格。
使用内置的reverse过程会受到惩罚，该过程在时间复杂度上是O(n)，在空间复杂度上为O(1)，看起来与此类似(是的，我们必须遍历列表直到最后，沿途创建反向链接(：
(define (reverse lst)
(let loop ((lst lst) (acc '()))
(if (null? lst)
acc
; notice the tail recursion!
(loop (cdr lst) (cons (car lst) acc)))))
另一方面，我不会太担心，除非您正在操作的列表非常庞大，并且您的探查器表明reverse过程是一个瓶颈。
只需使用内置的，以简化代码——编写现有函数是函数式编程所鼓励的风格。在Scheme中，我们尝试以尾部递归的方式处理列表，即使这意味着反向创建列表，并且我们需要在最后调用reverse，这也是完全可以接受的。
想象一下简单的复制函数：
(define (copy1 lst)
(let loop ((lst lst) (acc '()))
(if (null? lst)
(reverse acc)
(loop (cdr lst) (cons (car lst) acc)))))
与你使用附加的一个：
(define (copy2 lst)
(let loop ((lst lst) (acc '()))
(if (null? lst)
acc
(loop (cdr lst) (append acc (list (car lst)))))))
append和reverse都是O(n(，这意味着它们迭代整个列表。复制的两个版本之间的区别在于，具有reverse的版本在末尾对所有元素执行一次操作，而append版本对每个元素调用append。这使得最后的版本O(n*n(比第一个版本O(n(效率低得多。有了一个大的列表，你会很快注意到这种差异。
现在回答你的问题。您应该使用针对您的任务优化的数据类型。如果你总是在列表的末尾添加一个列表，那么反过来做列表上的所有工作，等待reverse，直到你需要它。你甚至可以围绕它进行抽象。