我在 SICP 练习 3.16 中看到的每个解决方案似乎都是通过创建超过三对来作弊的。我的理解错在哪里？

Question

SICP 练习 3.16为读者提供了一个计算列表结构中的对数的完整过程：

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))

然后，它要求读者创建由三对组成的列表结构，使该过程返回：

1. 3
2. 4
3. 7
4. 永远不要回来。

任务#1 和#4 很简单；只需制作一个包含三个元素的普通列表并制作一个循环列表即可。然而，对于任务 #2 和 #4，我见过的每个解决方案似乎都通过创建超过三对来作弊。例如，Scheme Wiki给出了这些：

 (define x '(foo)) 
 (define y (cons x x)) 
 (define str2 (list y)) 
 (count-pairs str2) ; 4 

 (define x '(foo)) 
 (define y (cons x x)) 
 (define str3 (cons y y)) 
 (count-pairs str3) ; 7

 (define second (cons 'a 'b)) 
 (define third (cons 'a 'b)) 
 (define first (cons second third)) 
 (set-car! third second) 
 (count-pairs first)  ;; => 4 
  
 (define third (cons 'a 'b)) 
 (define second (cons third third)) 
 (define first (cons second second)) 
 (count-pairs first)  ;; => 7 

我出于同样的原因不同意他们所有人的观点：他们似乎超过三对。例如，第一个代码块的最终列表将为(cons (cons (cons 'foo nil) (cons 'foo nil)) nil). 由于我已经写了cons三遍以上，所以这不是由三对组成的。同样，最后一个区块显然是(cons (cons (cons 'a 'b) (cons 'a 'b)) (cons (cons 'a 'b) (cons 'a 'b)))，远不止三对。

我的理解错在哪里？

Answer 1

将其写为

(define x    (cons 'foo '()))
(define y    (cons x x))
(define str2 (cons y '()))

几个conses？三个conses！但是当我们数它们时，x被数了两次，所以(cons x x) ==> (+ 1 1 1) = 3然后(cons y '()) => (+ 3 1) = 4。但那里仍然恰好有三个cons新生成的细胞。

将其写为

(define x    (cons 'foo '())) 
(define y    (cons x x)) 
(define str3 (cons y y)) 

几个conses？三个conses！但是当我们数它们时，x并且y被数了两次，所以(cons x x) ==> (+ 1 1 1) = 3然后(cons y y) => (+ 3 3 1) = 7……。但那里仍然只有三个cons新造的细胞。

这两个示例利用了列表结构共享。由 持有的 cons 单元的 和 字段都指向由car持有的同一个 cons 单元。cdryx

但程序并不知道这一点。它进入同一个 cons 单元x两次，并对其进行两次计数。

它可以测试相同性，与eq?. (eq? (car y) (cdr y))会回来的#t。但它不会拨打这个电话。

str2和持有的两个列表结构str3可以表示为 -- 第一个，第一个，为 --

 str2   -->  [ y | [] ]       ; first CONS cell
               |
               |
               [ x | x ]          ; second CONS cell
                 \   /
                  \ /
                   [ FOO | [] ]      ; third CONS cell

当你写作时，(cons (cons (cons 'foo nil) (cons 'foo nil)) nil)你是按价值写出同样的东西，但不是按结构写。

值相等性通过equal?- 例如，“打印出来的两个东西相同吗？当通过纯粹的手段观察时它们无法区分吗？...”（纯粹在这里意味着，不使用eq?）。

结构相等性通过检查eq?——例如，“这两个东西在计算机内存中实际上是同一件事吗？ ......”

“纯”函数式编程关注的是抽象“值”。

非纯编程关注计算机内存中的具体结构。

另一个值是

 str3   -->  [ y | y ]
               \   /
                \ /
                 [ x | x ]
                   \   /
                    \ /
                     [ FOO | [] ]