; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 07/27/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.2.22
;; 在Louis Reasoner的两个迭代算法中， things是有待处理的list， answer是积累
;; 下来的中间结果。
;; 算法(1)的问题在于： 根据程序逻辑， iter不断地从things序列中取得第一个item，
;; 然后经过square的处理，将结果积累到answer中，越在前面的item就越先被处理。
;; 因此如果要保持原来的顺序，任何一次iter的结果都应该放在“已”处理过的answer的后面
;; 而不是前面。
;; 算法(2)的问题在于： 尽管顺序是对了，但在cons构造新的list时，是用一个list作为
;; 头元素去连接后面的单个元素，即(cons a-list a-item)， 这样的结果不是list而是
;; 普通的pair。从specification的角度讲，对于这样的一个"list"应用car的结果不再
;; 是头元素而是头序列（除了尾元素以外的前面的序列），对于这样的一个"list"应用cdr
;; 的结果不再是尾序列而是尾元素。因此对这样一个"list"进行递归运算，实际上的顺序
;; 还是从尾元素开始到头元素结束，和算法(1)中的效果一样。而且它的cdr相当于正常list
;; 的car，它的car相当于正常list的cdr。
;; 比如：
;; a = (cons 1 (cons 2 (cons 3 ()))) = (1.(2.(3.()))) = (list 1 2 3)
;; b = (cons (cons (cons () 1) 2) 3) = (((().1).2).3) != (list 1 2 3)
;; (car a) = (cdr b) = 1
;; (car (cdr a)) = (cdr (car b)) = 2
;; (car (cdr (cdr a))) = (cdr (car (car b))) = 3
;; 个人认为这个问题是无法避免的，因为:
;; 对于list的递归访问，我们总是从头元素开始到尾元素结束
;; 对于list的递归构造，我们总是从尾元素开始到头元素结束
;; 这样，要保持顺序，就不可避免地需要额外的空间(递归中的存储)或时间(逆向结果然后reverse)
;; 用算法一保持逆序的结果或许在实践中是个更好的选择，因为很多场合中顺序可能不重要，或者
;; 可以在后面的其他函数作用(比如另一个iter模式的逆序map)自动转换回来而没有额外的代价；
;; 而且，即使必须使用正序的情况下，算法一(O(n))加上一个reverse操作(O(n))，其时间复杂度
;; 依然是O(n)，相当于对每个元素的构造多出很小一点的常量c。
