SICP Section 3.3 Modeling with Mutable Data

Exercise 3.12. The following procedure for appending lists was introduced in section 2.2.1:
(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y))))
Append forms a new list by successively consing the elements of x onto y. The procedure append! is similar to append, but it is a mutator rather than a constructor. It appends the lists by splicing them together, modifying the final pair of x so that its cdr is now y. (It is an error to call append! with an empty x.)
(define (append! x y) (set-cdr! (last-pair x) y) x)
Here last-pair is a procedure that returns the last pair in its argument:
(define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x))))
Consider the interaction
(define x (list 'a 'b)) (define y (list 'c 'd)) (define z (append x y)) z (a b c d) (cdr x) <response> (define w (append! x y)) w (a b c d) (cdr x) <response>
What are the missing <response>s? Draw box-and-pointer diagrams to explain your answer.

Answer:
(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y)))) (define (append! x y) (set-cdr! (last-pair x) y) x) (define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x))))
Exercise 3.13. Consider the following make-cycle procedure, which uses the last-pair procedure defined in exercise 3.12:
(define (make-cycle x) (set-cdr! (last-pair x) x) x)
Draw a box-and-pointer diagram that shows the structure z created by
(define z (make-cycle (list 'a 'b 'c)))
What happens if we try to compute (last-pair z)?

Answer: Terrible things happen! Make-cycle creates a circular list. This is not a bad thing to have and might actually come useful under some circumstances. However trying to compute (last-pair z) throws the interpreter into an infinite loop.

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.

Answer:
(define length-3 (cons (list 'a) (list 'b))) (count-pairs length-3) 3 (define length-4 (list (list 'a) (list 'b))) (count-pairs length-4) 4 (define x (cons (list 'a) (list 'b))) (define length-7 (cons x x)) (count-pairs length-7) 7
Exercise 3.18. Write a procedure that examines a list and determines whether it contains a cycle, that is, whether a program that tried to find the end of the list by taking successive cdrs would go into an infinite loop. Exercise 3.13 constructed such lists.

Answer:
(define (is-circular? x) (define (iter y) (cond ((null? y) false) ((eq? (car x) (car y)) true) (else (iter (cdr y))))) (iter (cdr x))) (define z (make-cycle (list 'a 'b 'c))) (is-circular? z) #t