(੭ु´･ω･`)੭ु⁾⁾

演習問題淡々と。
3章を読んでいるのですが、ここら辺でSchemeの肝になってる静的スコープと説明と動的なデータをどうやっていじるかの説明が入っている感じです。
今回は3.3章のMutable Data Structureのところを読んでいます。

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Exercise 3.12

(define (last-pair x) (if (null? (cdr x)) x (last-pair (cdr x))))
;; The procedure which changes (a. b. c. .. z) to (z)
(define x (list 'a 'b))
(define y (list 'c 'd))
(define (append x y) (if (null? x) y (cons (car x) (append (cdr x) y))))
(define (append! x y) (begin (set-cdr! (last-pair x) y) x))
(cdr x)
(begin (append! x y) (cdr x))
;; create local environemnt to compute (last-pair x)
;; compare (begin (append x y) x) and (begin (append! x y) x)

;; xがappend!で新しく置き換わるというだけで面白い話ではない

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Exercise 3.13

(define (make-cycle x) (set-cdr! (last-pair x) x) x)
(define z (make-cycle (list 'a 'b 'c)))
(begin (display (car z))
       (newline) (display (cadr z))
       (newline) (display (caddr z))
       (newline) (cadddr z))
;; gosh> a b c a
;; i.e. z = the loop (a b c a b c a b c ...)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Exercise 3.14

(define (mystery x)
  (define (loop a b)
    (if (null? a) b
	(let ((temp (cdr a))) (set-cdr! a b) (loop temp a))))
  (loop x '()))
(define (v y)
  (define (f x y) (if (= x y) () (cons x (f (+ x 1) y))))
  (f 0 y))
(define w (mystery (v 10))) ;; reverse of list
;; (0 1 2 .. 8 9) -> (9 8 7 .. 1 0)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Exercise 3.18-19

;; 3.18 Find a procedure that determines whether a list contains a cycle

(define (have-cycle? x)
  (define (exists? b xs)
    (cond ((null? xs) #f)
	  ((b (car xs)) #t)
	  (else (exists? b (cdr xs)))))
  (define (exists-self-ref? x ys)
      (if (exists? (lambda (y) (eq? x y)) ys) #t
	  (begin (set! ys (cons x ys)) (exists-self-ref? (cdr x) ys))))
  (exists-self-ref? x ()))

;; 追記. exists? の代わりに memq 使えばもっとすっきりした感じ

(define v (cons 0 ()))
(begin (set-cdr! v v) v) ;; loop (0 0 0 ..)
(define x (cons 0 (cons 1 ())))
(begin (set-cdr! (cdr x) x) (set! x (cons 1 x))) ;; loop (1 0 1 0 1 ..)
(have-cycle? v) ;; true
(have-cycle? x) ;; true
;; ys=(list x) -> (list (cdr x) x) -> (list (cdr (cdr x)) (cdr x) x) -> (list (cdr (cdr (cdr x))) (cdr (cdr x)) (cdr x) x)
;; Then we have True since (eq? (cdr (cdr (cdr x))) (cdr x)) = true.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; 3.19 implement 3.18 with constant space

(define (have-cycle1? x)
  (define (count b x)
    (cond ((null? x) 0)
	  ((not (b x)) (count b (cdr x)))
	  ((b x) (+ (count b (cdr x)) 1))))
  (define (exists-self-ref? x y depth)
      (if (>= (count (lambda (y) (eq? x y)) x) 2) #t
	  (exists-self-ref? x (cdr y) (+ depth 1))))
  (exists-self-ref? x x 0))

(have-cycle1? v) ;; true
(have-cycle1? x) ;; true

若干注釈で、コンスタントスペースの解釈を入力xに対して、その計算の領域が|x|の定数倍程度で済むと解釈しました。
おそらく、3.18だとysの領域確保に|x|の2乗程度の領域を使っているので、それを改善しますという文脈の話です。
ここで書いたprocedureだと、successive cdrの結果全部を記憶する代わりに、successive cdrを何回適用したかのみを記憶して領域を節約している感じです。
ただ、計算時間と計算領域は常にトレードオフの関係にあるので、これが真に改善になっているかは何とも言えません。

とまあこんな感じでだらだら。
あとはつまんない感じだったので、省略します。