; 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)))