#|
  Упражнение 3.16

  Бен Битобор решил написать процедуру для подсчета числа пар в любой списковой структуре. «Это легко,
  — думает он. — Число пар в любой структуре есть число пар в car плюс число пар в cdr плюс один на
  текущую пару». И он пишет следующую процедуру:

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

  Покажите, что эта процедура ошибочна. В частности, нарисуйте диаграммы, представляющие списковые
  структуры ровно из трех пар, для которых Бенова процедура вернет 3; вернет 4; вернет 7; вообще никогда
  не завершится.
|#

(#%require rackunit)

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

(define x (cons 'a 'b))
(define y (cons 'c 'd))
(define C3 (cons x y))

(check-equal? (count-pairs C3) 3)

(define z (cons 'c x))
(define C4 (cons z x))

(check-equal? (count-pairs C4) 4)

(define w (cons x x))
(define C7 (cons w w))

(check-equal? (count-pairs C7) 7)

(define inf (cons 'c x))
(define Cinf (cons x inf))
(set-cdr! inf Cinf)

;(count-pairs Cinf)

#|
          ┏━━━┳━━━┓   ┏━━━┳━━━┓
    C3 ──►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃
          ┗━┿━┻━━━┛   ┗━┿━┻━━━┛
            │           └────────────────┐
            ▼                            ▼
          ┏━━━┳━━━┓   ┏━━━┳━━━┓        ┏━━━┳━━━┓   ┏━━━┳━━━┓
    x ───►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃  y ───►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃
          ┗━┿━┻━━━┛   ┗━┿━┻━━━┛        ┗━┿━┻━━━┛   ┗━┿━┻━━━┛
            ▼           ▼                ▼           ▼
          ┏━━━┓       ┏━━━┓            ┏━━━┓       ┏━━━┓
          ┃ a ┃       ┃ b ┃            ┃ c ┃       ┃ d ┃
          ┗━━━┛       ┗━━━┛            ┗━━━┛       ┗━━━┛

          ┏━━━┳━━━┓   ┏━━━┳━━━┓
    C4 ──►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃
          ┗━┿━┻━━━┛   ┗━┿━┻━━━┛
            │           └────────────────┐
            ▼                            ▼
          ┏━━━┳━━━┓   ┏━━━┳━━━┓        ┏━━━┳━━━┓   ┏━━━┳━━━┓
    z ───►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃  x ───►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃
          ┗━┿━┻━━━┛   ┗━┿━┻━━━┛      ┌►┗━┿━┻━━━┛   ┗━┿━┻━━━┛
            ▼           └────────────┘   ▼           ▼
          ┏━━━┓                        ┏━━━┓       ┏━━━┓
          ┃ c ┃                        ┃ a ┃       ┃ b ┃
          ┗━━━┛                        ┗━━━┛       ┗━━━┛

          ┏━━━┳━━━┓   ┏━━━┳━━━┓
    C7 ──►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃
          ┗━┿━┻━━━┛   ┗━┿━┻━━━┛
            │ ┌─────────┘
            ▼ ▼
          ┏━━━┳━━━┓   ┏━━━┳━━━┓
    w ───►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃
          ┗━┿━┻━━━┛   ┗━┿━┻━━━┛
            │ ┌─────────┘
            ▼ ▼
          ┏━━━┳━━━┓   ┏━━━┳━━━┓
    x ───►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃
          ┗━┿━┻━━━┛   ┗━┿━┻━━━┛
            ▼           ▼
          ┏━━━┓       ┏━━━┓
          ┃ a ┃       ┃ b ┃
          ┗━━━┛       ┗━━━┛

            ┌────────────────────────────────────────┐
            ▼                                        │
          ┏━━━┳━━━┓   ┏━━━┳━━━┓                      │
    Cinf─►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃                      │
          ┗━┿━┻━━━┛   ┗━┿━┻━━━┛                      │
            │           └────────────────┐           │
            ▼                            ▼           │
          ┏━━━┳━━━┓   ┏━━━┳━━━┓        ┏━━━┳━━━┓   ┏━┿━┳━━━┓
    x ───►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃  inf ─►┃ • ┃ • ╂──►┃ • ┃ ╱ ┃
          ┗━┿━┻━━━┛   ┗━┿━┻━━━┛        ┗━┿━┻━━━┛   ┗━━━┻━━━┛
            ▼           ▼                ▼
          ┏━━━┓       ┏━━━┓            ┏━━━┓
          ┃ a ┃       ┃ b ┃            ┃ c ┃
          ┗━━━┛       ┗━━━┛            ┗━━━┛
|#