SICP Exercise 3.16 gives the reader a broken procedure for counting the numbers of pairs in a list structure:
(define (count-pairs x)
(if (not (pair? x))
0
(+ (count-pairs (car x))
(count-pairs (cdr x))
1)))
It then challenges the reader to create list structures made up of exactly three pairs that make this procedure return:
Tasks #1 and #4 are easy; Just make a normal list of three elements and make a circular list. For tasks #2 and #4, however, every solution that I've seen appears to cheat by creating more than three pairs. For example, the Scheme Wiki gives these:
(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
I disagree with all of them for the same reason: They appear to be more than three pairs. For example, the final list from the first block of code will be (cons (cons (cons 'foo nil) (cons 'foo nil)) nil). As I've written cons more than three times, this isn't made of three pairs. Similarly, the last block is clearly (cons (cons (cons 'a 'b) (cons 'a 'b)) (cons (cons 'a 'b) (cons 'a 'b))), which is far more than three pairs.
Where is my misunderstanding?
Write it as
(define x (cons 'foo '()))
(define y (cons x x))
(define str2 (cons y '()))
How many conses? Three conses! But when we count them, x is counted twice, so (cons x x) ==> (+ 1 1 1) = 3 and then (cons y '()) => (+ 3 1) = 4. But still there are exactly three cons cells freshly minted there.
Write it as
(define x (cons 'foo '()))
(define y (cons x x))
(define str3 (cons y y))
How many conses? Three conses! But when we count them, x and y are counted twice, so (cons x x) ==> (+ 1 1 1) = 3 and then (cons y y) => (+ 3 3 1) = 7. But still there are just three cons cells freshly minted there.
The two examples exploit list structure sharing. Both car and cdr fields of the cons cell held by y point to the same cons cell, held by x.
But the program does not know that. It enters the same cons cell -- x -- twice, and counts it twice.
It could test for the sameness, with eq?. (eq? (car y) (cdr y)) would return #t. But it doesn't make this call.
The two list structures, held by str2 and str3, can be represented as -- the first one, first, as --
str2 --> [ y | [] ] ; first CONS cell
|
|
[ x | x ] ; second CONS cell
\ /
\ /
[ FOO | [] ] ; third CONS cell
When you write (cons (cons (cons 'foo nil) (cons 'foo nil)) nil) you're writing out the same thing by value, but not structurally.
Value equality is checked with equal? -- as in, "are the two things printed out the same? Are they indistinguishable when observed by pure means?..." (pure here means, not employing eq?).
Structure equality is checked with eq? -- as in, "are the two things actually the same thing in computer memory?..."
"Pure" functional programming concerns itself with abstract "values".
Impure programming concerns itself with concrete structures in computer memory.
And the other value is
str3 --> [ y | y ]
\ /
\ /
[ x | x ]
\ /
\ /
[ FOO | [] ]