首页 > 代码库 > SICP 习题 (2.22)解题总结: 迭代过程中的列表处理

SICP 习题 (2.22)解题总结: 迭代过程中的列表处理

SICP 习题 2.22是习题2.21的后续题目,题目中讲到叫Louis Reasoner的人想重写suqare-list过程,希望使用迭代计算过程,而不是递归计算过程,有关迭代计算过程和递归计算过程,如果你没什么印象了,请翻回习题1.9 的解题总结看看。


那个叫Louis Reasoner的人写的迭代版的suqre-list是这样的:


(define (square-list-revert items)
  (define (iter things answer)
    (if (null? things)
	answer
	(iter (cdr things)
	      (cons (square (car things))
		    answer))))
  (iter items ‘()))


然后他发现这个过程有些问题,所有平方数的顺序反了。


于是他又将过程改成这样:


(define (square-list-revert-2 items)
  (define (iter things answer)
    (if (null? things)
	answer
	(iter (cdr things)
	      (cons answer
		    (square (car things))))))
  (iter items ‘()))


结果还是不对,这次返回的平方数的顺序是对了,不过格式有问题,没有形成一个列表,而是形成了一个嵌套的列表。。。。


题目要求我们解释为什么。

如果把以上的返回值打印出来,我觉得很多程序员都会明白是为什么:


1 ]=> (square-list-revert-2 ‘(1 2 3 4))

;Value 2: ((((() . 1) . 4) . 9) . 16)


可以看到,Louis其实是将() 和 1 连接在一起,应为后面没有nil,所以这个变成了一个序对(() . 1),然后又将序对(()  .  1) 和 4 连接起来,继续形成新的序对。。。。。


最后,如果一定要使用Louis的代码进行修改,完成相同的功能的话,可以使用append过程代替cons过程,将代码写成这样:

(define (square-list-revert-right items)
  (define (iter things answer)
    (if (null? things)
	answer
	(iter (cdr things)
	      (append answer
		    (list (square (car things)))))))
  (iter items ‘()))


不过,如果我们考虑的是效率的话,使用append并不是一个好主意,大家可以想一想为什么。


SICP 习题 (2.22)解题总结: 迭代过程中的列表处理