练习 2.39

通过研究 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

要使用 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-leftfold-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 操作的更多资料。

讨论

blog comments powered by Disqus