SICP 練習 3.16為讀者提供了一個計算串列結構中對數的錯誤程式：
(define (count-pairs x)
(if (not (pair? x))
0
( (count-pairs (car x))
(count-pairs (cdr x))
1)))
然后它挑戰讀者創建由三對組成的串列結構，使這個程序回傳：
- 3
- 4
- 7
- 永遠不要回來。
任務#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)))是 ，遠遠超過三對。
我的誤解在哪里？
uj5u.com熱心網友回復：
寫成
(define x (cons 'foo '()))
(define y (cons x x))
(define str2 (cons y '()))
有多少個騙局？三連敗！但是當我們計算它們時，x會被計算兩次，so (cons x x) ==> ( 1 1 1) = 3and then (cons y '()) => ( 3 1) = 4。但是那里仍然恰好有三個cons新鑄造的細胞。
寫成
(define x (cons 'foo '()))
(define y (cons x x))
(define str3 (cons y y))
有多少個騙局？三連敗！但是當我們計算它們時，它們x被y計算了兩次，所以(cons x x) ==> ( 1 1 1) = 3然后(cons y y) => ( 3 3 1) = 7。但是那里仍然只有三個cons新鑄造的細胞。
這兩個示例利用串列結構共享。car由 持有的 cons 單元格的和cdr欄位都指向y由 持有的同一個 cons 單元格x。
但是程式不知道這一點。它進入同一個 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 | [] ]
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/413377.html
標籤：