関数型言語の勉強にSICPを読もう - (31) 3章 - 標準部品化力、オブジェクトおよび状態 (152ページ)

問題3.17

3日くらいずっと考えていた。

(define (count-pairs x)
  (let ((already? '()))
    (define (count-pairs-internal y)
      (let ((add-count 0))
        (if (not (pair? y))
            0
            (begin
              (if (not (memq y already?))
                  (begin (set! add-count 1) (set! already? (cons y already?)))
                  (set! add-count 0))
              (+ (count-pairs-internal (car y))
                 (count-pairs-internal (cdr y))
                 add-count)))))
    (count-pairs-internal x)))

;; 3
(define a (cons 'x (cons 'x (cons 'x 'x))))
(display (count-pairs a))
(newline)

;; 4
(define a (cons 'x 'x))
(define b (cons 'y a))
(define c (cons a b))
(display (count-pairs c))
(newline)

;; 7
(define a (cons 'x 'x))
(define b (cons a a))
(define c (cons b b))
(display (count-pairs c))
(newline)

最初から頭の中に正解に近いイメージがあったのだが、memqの引数を逆に渡しているのに気づかずはまる
あとは、add-countのスコープを1つ上にしてしまい、再帰的に書き換えられてはまる。
などなどの、はまりポイントをくぐったのでデバッグノウハウがたまりました。

※「SICPを読もう」の目次はこちら