Exercise 3.16. Ben Bitdiddle decides to write a procedure to count the number of pairs in any list structure. ‘‘It’s easy,‘’ he reasons. ‘‘The number of pairs in any structure is the number in the car plus the number in the cdr plus one more to count the current pair.‘’ So Ben writes the following procedure:
(define (count-pairs x)
(if (not (pair? x))
0
(+ (count-pairs (car x))
(count-pairs (cdr x))
1)))
Show that this procedure is not correct. In particular, draw box-and-pointer diagrams representing list structures made up of exactly three pairs for which Ben’s procedure would return 3; return 4; return 7; never return at all.
下面的情况是能产生正确结果的：
x +---+---+ +---+---+ +---+---+
------>| | +----->| | +----->| | / |
+-+-+---+ +-+-+---+ +-+-+---+
| | |
| | |
v v v
+---+ +---+ +---+
| 1 | | 2 | | 3 |
+---+ +---+ +---+一旦更改过列表的前后指针之后，这个过程就产生错误的结果。
会错误计算为 4 的例子：
x +---+---+ +---+---+
-------->| | +------->| | / |
+-+-+---+ +-+-+---+
| |
| |
v |
+---+---+ |
| | / |<---------+
+-+-+---+
|
|
v
+---+
| 1 |
+---+会计算成 5 的例子：
x +---+---+ +---+---+
-------->| | +------->| | |
+-+-+---+ +-+-+-+-+
| | |
| | |
v | |
+---+---+ | |
| | / |<---------+---+
+-+-+---+
|
|
v
+---+
| 1 |
+---+会计算成 7 的例子：
+---+---+
| | |
+-+-+-+-+
| |
v v
+---+---+
| | |
+-+-+-+-+
| |
v v
+---+---+
| | |
+-+-+---+
|
|
v
+---+
| 1 |
+---+
下面是代码与测试用例
(define (count-pairs x)
(if (not (pair? x))
0
(+ (count-pairs (car x))
(count-pairs (cdr x))
1)))
(define count3 (list 1 2 3))
(define count4
(let ((pairs (list 1 2 3)))
(begin
(set-car! pairs (cddr pairs))
pairs)))
(define count5
(let ((pairs (list 1 2 3)))
(begin
(set-car! pairs (cddr pairs))
(set-car! (cdr pairs) (cddr pairs))
pairs)))
(define count7
(let ((pairs (list 1 2 3)))
(begin
(set-car! pairs (cdr pairs))
(set-car! (cdr pairs) (cddr pairs))
pairs)))
;;; tests begin
(load "../testframe.scm")
(assert= (count-pairs count3) 3)
(assert= (count-pairs count4) 4)
(assert= (count-pairs count5) 5)
(assert= (count-pairs count7) 7)