SICP Exercise 3.17 correct count-pairs

Exercise 3.17.  Devise a correct version of the count-pairs procedure of exercise 3.16 that returns the number of distinct pairs in any structure. (Hint: Traverse the structure, maintaining an auxiliary data structure that is used to keep track of which pairs have already been counted.)

SOLUTION

The code is here:

 Exercise 3.17 correct count-pairs

The explanation and the box-and-pointer diagram is here:

 Diagram


Comments

Post a Comment

Popular posts from this blog

SICP Exercise 1.22 search-for-primes

Image
Exercise 1.22.    Most Lisp implementations include a primitive called  runtime  that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following  timed-prime-test  procedure, when called with an integer  n , prints  n  and checks to see if  n  is prime. If  n  is prime, the procedure prints three asterisks followed by the amount of time used in performing the test. (define (timed-prime-test n)   (newline)   (display n)   (start-prime-test n (runtime))) (define (start-prime-test n start-time)   (if (prime? n)       (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time)   (display " *** ")   (display elapsed-time)) Using this procedure, ...
Read more

SICP Exercise 3.45 deadlock

Exercise 3.45.   Louis Reasoner thinks our bank-account system is unnecessarily complex and error-prone now that deposits and withdrawals aren't automatically serialized. He suggests that  make-account-and-serializer  should have exported the serializer (for use by such procedures as  serialized-exchange ) in addition to (rather than instead of) using it to serialize accounts and deposits as  make-account  did. He proposes to redefine accounts as follows: (define (make-account-and-serializer balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amoun...
Read more

SICP Exercise 4.7 let*

Exercise 4.7.    Let*  is similar to  let , except that the bindings of the  let  variables are performed sequentially from left to right, and each binding is made in an environment in which all of the preceding bindings are visible. For example (let* ((x 3)        (y (+ x 2))        (z (+ x y 5)))   (* x z)) returns 39. Explain how a  let*  expression can be rewritten as a set of nested  let  expressions, and write a procedure  let*->nested-lets  that performs this transformation. If we have already implemented  let  (exercise  4.6 ) and we want to extend the evaluator to handle  let* , is it sufficient to add a clause to  eval  whose action is (eval (let*->nested-lets exp) env) or must we explicitly expand  let*  in terms of...
Read more