断断续续读到SICP第三章，觉得scheme有点入门了，不过长久不练习，脑子又不能适应函数式编程模式了，觉得3.17、3.18、3.19还比较有意思，贴个自己的解题思路吧。
3.17
(define (count-unique-pair x)
(let ((db (cons 0 0)))
(define (count-pair x)
(define (add-unique-pair x db1)
(define (add-record db0 x)
(set-car! db0 x)
(set-cdr! db0 (cons 0 0))
x)
(define (find-record x db0)
(if (not (pair? (car db0)))
(add-record db0 x)
(if (eq? x (car db0))
'()
(find-record x (cdr db0)))))
(find-record x db1))
(if (not (pair? x))
0
(if (null? (add-unique-pair x db))
0
(+ (count-pair (car x))
(count-pair (cdr x))
1))))
(count-pair x)))
(define xx '(a b))
(define z1 (cons xx xx))
(define z2 (cons '(a b) '(a b)))
(count-unique-pair z1)
实现比较丑陋，基本还是过程式编程，使用了一个db存储已经遍历过的pair，可以对付带环的表，而且只要此pair已经遍历过，则其子pair也不在遍历了。相比一下纯函数式写法，这种方式还是比较清晰且容易理解的，不过存在内存竞争问题，不能并行运行。
3.18
此题简化了一些，不用考虑car的环，使用3.17的存储做法就OK了。
3.19
这个需要个小trick，要空间常量，意味着不能存储已遍历的pair指针，那我就用时间换空间吧，使用两个指针，A指针一次步进1个pair，B指针一次步进2个pair，如果存在环，B指针会再次追上A指针，每次步进判断指针是否相等就可以知道是否带环了：）
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。