; A solution to the count-pairs problem (#3.17) ; ; Note the use of a list to keep track of which pairs ; have already been visited. (define (count-pairs pair) ; Establish a state variable, visited-pairs, that maintains ; a list of memory locations that have already been traversed. ; The complexity of where, specifically, pairs are placed in ; memory is hidden from you by Scheme, but whenever we draw an ; arrow in a box-and-pointer diagram, the arrow is a reference ; to somewhere in memory where useful stuff is stored. (let ((visited-pairs '())) ; visited? takes a pair and a list as inputs and returns #t ; if the pair is in the list, #f otherwise. For this problem, ; the list will receive visited-pairs as its argument. (define (visited? p l) (cond ((null? l) #f) ((eq? p (car l)) #t) (else (visited? p (cdr l))))) ; cph (short for count-pairs-helper) works as the comments show: (define (cph p) ; if the input is not a pair or it has already been ; visited, do not count it as a new pair (cond ((or (not (pair? p)) (visited? p visited-pairs)) 0) ; otherwise, it is a pair that has not been visited, so ; * update the visited-pairs list to indicate this and ; * count this pair as 1 and add that to all unvisited ; pairs that the car and cdr may lead to (else (set! visited-pairs (cons p visited-pairs)) (+ 1 (cph (car p)) (cph (cdr p)))))) ; Use the helper function to find the number of unique pairs ; that the input to count-pairs leads to (cph pair)))