Exercise-3-17

Упражнение 3.17.

Напишите правильную версию процедуры count-pairs из упражнения 3.16, которая возвращает

число различных пар в любой структуре.

Решение

(define (count-pairs x)

  (define (contains? what where)

    (cond

      ((null? where) #f)

      ((eq? what (car where)) #t)

      (else (contains? what (cdr where)))))

  (let ((found '()))

    (define (helper x)

      (if (and (pair? x) (not (contains? x found)))

          (begin

            (set! found (cons x found))

            (+ 1 (helper  (car x)) (helper  (cdr x))))

          0))

    (helper x)))

Интересный прием заключен в конструкции

(set! found (cons x found))

В целом, весьма понятно что она делает, поэтому предлагается рассмотреть ее читателю самостоятельно.

Тест конструкции 

(define a (cons 1 2))

(define b (cons 3 a))

(define c (cons b a))

(set-cdr! a c)

(count-pairs c) ;3

Работает)

PS 2 упражнения с диаграммками пропущены.