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

Question

SICP Exercise 3.16 为 reader 提供了一个用于计算列表结构中对数的错误过程：

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

然后它挑战 reader 创建由 正好三对 组成的列表结构，使得此过程 return:

3
4
7
从不return.

任务 #1 和 #4 很简单；只需制作一个包含三个元素的普通列表并制作一个循环列表即可。然而，对于任务 #2 和 #4，我所见过的每个解决方案似乎都通过创建超过三对来作弊。例如，the 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 '()))

有多少个 cons？三个 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))

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

这两个示例利用了列表结构共享。 y持有的cons cell的car和cdr字段都指向x持有的同一个cons cell。

但程序不知道。它进入同一个 cons 单元格 -- x -- 两次，并计算两次。

它可以测试相同性，eq?。 (eq? (car y) (cdr y)) 会 return #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 | [] ]

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

Every solution that I've seen for SICP Exercise 3.16 appears to cheat by creating more than three pairs. Where is my misunderstanding?

scheme

list

sicp

cons