SICP問題3.16

SICP

Ben Bitdiddleが書いたリスト構造中の対の個数を数える手続き

(define (count-pairs x)
  (if (not (pair? x))
      0
      (+ (count-pairs (car x))
         (count-pairs (cdr x))
         1)))

三つの対で出来ているリスト構造で3を返すもの, 4を返すもの, 7を返すもの, 何も返さないものを表現する箱とポインタ図で描けという問題だが、問題の「三つの対で出来ているリスト構造」という部分が良く分からん。
Webで他の人の回答見てみても何だか良く分からないし…。と思ってググったら

難しい。はじめ「三つの対で出来ているリスト構造」の意味が分からなかった。
要は図にした時にcons箱が三つあるデータ構造の事らしい。
つまり、三つの箱の間でcarとcdrのポインタを繋げあって題意を満たすようなものを
作れば良い。リストって言うから木はダメなのかと思ったけど違った。

考えすぎると頭がかゆくなる SICP３章の解答 3.1〜3.23

という記述を見つけて納得。しかし、どうして皆、あの一文で理解できるんだろ?不思議だ。
ということで、箱とポインタ図で箱3つとそこから出ている矢印の本数が3,4,7本のものを考えてみる。

3が返って来るリスト構造

(define l3 (list 'a 'b 'c))
; l3
l3
; (a b c)
(count-pairs l3)
; 3

箱とポインタ図

   1     2     3
l3→□□→□□→□■
  　↓　　↓　　↓
  　a 　　b 　　c

4が返って来るリスト構造

(define x (cons 'a '()))
; x
x
; (a)
(define y (cons 'b x))
; y
y
; (b a)
(define l4 (cons y x))
; l4
l4
; ((b . #0=(a)) . #0#)
(count-pairs l4)
; 4

箱とポインタ図

  　　　　　a 
   1　　 2　↑
l4→□□─→□■
    │　　　↑4
   3↓┌──┘
  　□□
  　↓
  　b

7が返って来るリスト構造

(define x (cons 'a '()))
; x
x
; (a)
(define y (cons x x))
; y
y
; (#0=(a) . #0#)
(define l7 (cons y y))
; l7
l7
; (#0=(#1=(a) . #1#) . #0#)
(count-pairs l7)
; 7

箱とポインタ図

  　　　　　a 
   1　　　　↑
l7→□□　　□■
   2├┘3  5↑
  　↓┌──┤
  　□□　　│ 4, 5の部分が2回カウントされるので、5+2で7
  　└───┘
      4

結果が返って来ないリスト構造

(define ll (make-cycle (list 'a 'b 'c)))
; ll
ll
; #0=(a b c . #0#)
; (display ll) すると無限ループするので注意。
(count-pairs ll)
; 無限ループで返って来ない。

箱とポインタ図

  　┌───────┐
  　↓　　　　　　　│
ll→□□→□□→□□┘
  　↓　　↓　　↓
  　a 　　b 　　c