通过研究 fold-left 的定义（在练习 2.38），可以看出 fold-left 的展开规则为（使用列表 (list 1 2 3 4) 作为例子）：
(fold-left f '() (list 1 2 3 4))
(... (f '() 1) ...)
(... (f (f '() 1) 2) ...)
(... (f (f (f '() 1) 2) 3) ...)
(f (f (f (f '() 1) 2) 3) 4)
而要生成列表的逆序，我们需要这样一个计算序列（依然使用列表 (list 1 2 3 4) 作例子）：
(reverse (list 1 2 3 4))
(... (cons 1 '()) ...)
(... (cons 2 (cons 1 '())) ...)
(... (cons 3 (cons 2 (cons 1 '()))) ...)
(cons 4 (cons 3 (cons 2 (cons 1 '()))))
可以看出，这两个计算序列非常相似，唯一的不同就是函数 f 和函数 cons 的参数位置不同，不过这个问题并不难解决，只要在函数体内调整两个参数的位置就行了：
(lambda (x y)
(cons y x))
综合上面叙述，可以给出相应的函数：
;;; 39-reverse-using-fold-left.scm
(define (reverse sequence)
(fold-left (lambda (x y)
(cons y x))
'()
sequence))
测试：
1 ]=> (load "39-reverse-using-fold-left.scm")
;Loading "39-reverse-using-fold-left.scm"... done
;Value: reverse
1 ]=> (reverse (list 1 2 3 4))
;Value 11: (4 3 2 1)
测试所执行的表达式的展开过程和前面给出的展开过程完全一样。
要使用 fold-right 实现 reverse 函数，我们同样先分析 fold-right 的展开序列：
(fold-right f '() (list 1 2 3 4))
(f 1 ...)
(f 1 (f 2 ...))
(f 1 (f 2 (f 3 ...)))
(f 1 (f 2 (f 3 (f 4 ...))))
(f 1 (f 2 (f 3 (f 4 '()))))
要生成列表的逆序，我们需要让 fold-right 生成这样一个计算序列：
(reverse (list 1 2 3 4))
(fold-right g '() (list 1 2 3 4))
(... (g 4 '()) ...)
(... (g (g 4 '()) 3) ...)
(... (g (g (g 4 '()) 3) 2) ...)
(g (g (g (g 4 '()) 3) 2) 1)
要倒转函数的组合顺序，可以通过在函数体内调整参数的位置来做到这一点，在前面的 reverse 定义中我们已经看到了这一点：
(lambda (x y)
(g y x))
问题的关键就是找出函数 g ，从 fold-left 的经验看来， cons 很有可能就是 g ，而且 (cons 4 '()) 似乎也说得过去，不过当计算进展到第二步时，计算就变成了 (cons (cons 4 '()) 3) ，这时再用 cons 就说不通了，因此 cons 不是我们所寻找的函数 g 。
从 cons 失败的经验来看， g 应该不仅仅能处理单个元素，它还应该能将一个列表和单个元素组合起来形成一个新列表，这也就是书本 68 页介绍过的 append 函数：
1 ]=> (append (list 1 2 3) (list 4 5 6))
;Value 12: (1 2 3 4 5 6)
虽然 append 要求两个参数都是列表，但是让一个列表和单个元素组合起来也不太难，只要将单个元素转换成一个包含单个元素的列表就行了：
1 ]=> (append (list 1 2 3) 4) ; 组合单个元素
;Value 13: (1 2 3 . 4)
1 ]=> (append (list 1 2 3) (list 4)) ; 组合两个列表
;Value 14: (1 2 3 4)
这样的话，函数 g 的定义终于浮出水面了：
(lambda (x y)
(append y (list x)))
根据以上给出的条件，现在可以写出用 fold-right 实现的 reverse 函数了：
;;; 39-reverse-using-fold-right.scm
(define (reverse sequence)
(fold-right (lambda (x y)
(append y (list x)))
'()
sequence))
测试：
1 ]=> (load "39-reverse-using-fold-right.scm")
;Loading "39-reverse-using-fold-right.scm"... done
;Value: reverse
1 ]=> (reverse (list 1 2 3 4 5 6 7))
;Value 12: (7 6 5 4 3 2 1)
这个表达式的计算展开是：
(reverse (list 1 2 3 4 5 6 7))
(append '() (list 7))
(append '(7) (list 6))
(append '(7 6) (list 5))
(append '(7 6 5) (list 4))
(append '(7 6 5 4) (list 3))
(append '(7 6 5 4 3) (list 2))
(append '(7 6 5 4 3 2) (list 1))
'(7 6 5 4 3 2 1)
我们分别使用 fold-left 和 fold-right 两种方法定义了 reverse 函数，除了实现方面的不同外，它们的效率也有很大的区别：
fold-left 实现的 reverse 每次都递归地使用 cons 组合起一个元素和一个列表，每次组合操作的时间复杂度为 \(O(1)\) ，空间复杂度为 \(O(1)\) ，翻转整个列表所需的时间复杂度为 \(O(n)\) ，空间的复杂度也为 \(O(n)\) ，它是一个线性复杂度的线性递归过程。
另一方面， fold-right 实现的 reverse 每次都递归地使用 append 将一个列表和一个包含单个元素的列表组合起来，每次组合操作的时间复杂度为 \(O(n)\) ，空间复杂度为 \(O(1)\) ，翻转整个列表所需的时间复杂度为 \(O(n^2)\) ，而空间复杂度为 \(O(n)\) ，它是一个二次复杂度的线性递归过程。
See also
练习 2.38 的最后部分有关于 fold 操作的更多资料。