3.3.1 可変リスト構造

Exercise 3.12

appendとappend!の挙動の違い

手続きの定義

; xの一番最後の要素にyを付け加える
(define (append x y)
    (if (null? x)
        y
        (cons (car x) (append (cdr x) y))
    )
)

; xの最後の要素をとってきて、そこに追加する
(define (append! x y)
    (set-cdr! (last-pair x) y)
x)

(define (last-pair x)
    (if 
        (null? (cdr x))
        x
        (last-pair (cdr x))
    )
)

初期状態のポインタの状態

append実行の挙動

; append
(define x (list 'a 'b))
(define y (list  'c 'd))
(print "x:" x " y:" y)

(define z (append x y))
(print "(append x y) -> " z)

(print "(cdr x) -> " (cdr x))
;x:(a b) y:(c d)
;(append x y) -> (a b c d)
;(cdr x) -> (b)

append!実行の挙動

; append!
(define x (list 'a 'b))
(define y (list 'c 'd))
(print "x:" x " y:" y)

(define w (append! x y))
(print "(append! x y) -> " w)
(print "(cdr x) -> " (cdr x))
;x:(a b) y:(c d)
;(append! x y) -> (a b c d)
;(cdr x) -> (b c d)

Exercise 3.13

ぐーるぐる

(define (make-cycle x)
    (set-cdr! (last-pair x) x)
x)

(define z (make-cycle (list 'a 'b 'c)))
(print "z" z)
;z#0=(a b c . #0#)

(print "(last-pair z) -> " (last-pair z))

とまっちゃうー＞＜

Exercise 3.14

逆まわし

(define (mystery x)
    (define (loop x y)
        (if 
            (null? x)
            y
            (let 
                ((temp (cdr x)))
                (set-cdr! x y)
                (loop temp x)
            )
        )
    )
(loop x '()))

(define v (list 'a 'b 'c)) 
(define w (mystery v)) 

(print "w:" w)
; w:(c b a)

共有とアイデンティティ

(define x (list 'a 'b))
(define z1 (cons x x))
(define z2 (cons (list 'a 'b) (list 'a 'b)))
(define (set-to-wow! x) (set-car! (car x) 'wow) x)

(print (set-to-wow! z1))
;((wow b) wow b)

(print (set-to-wow! z2))
;((wow b) a b)

Exercise 3.15

Exercise 3.16

count-pairs で3,4,7が返るデータ構造をつくる & うまく動かないのはどんなときか。

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

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

(define l4 (cons 'a (cons 'b x)))
(print (count-pairs l4))
;4

(define l7 (cons 'a (cons 'b (cons x x))))
(print (count-pairs l7))
; 7

(define l_mevius (cons 'a (cons 'b (cons 'c ()))))
(set-cdr! (cdr (cdr l_mevius)) l_mevius)
;#0=(a b c . #0#)
;(print (count-pairs l_mevius))
;... 終了しない

Exercise 3.17

count-pairs ⼿続きの正しいバージョンを考え、任意の構造について区別可能なペアの数を返すようにせよ。(ヒント：カウント済みのペアを記録しておく補助データ構造を維持しながら構造をたどれ)。

(define (count-pairs x)
    (define mem '())
    (define (count x)
        (cond 
            ((not (pair? x)) 0)
            ((memq x mem) 0)
            (else
                (set! mem (cons x mem))
                (+ 
                    (count (car x))
                    (count (cdr x))
                    1
                )))
    )
(count x))


(print (count-pairs l3))
;3
(print (count-pairs l7))
;5
(print (count-pairs l_mevius))
;3

今まで辿ったリストを保持しておく。

Exercise 3.18

リストを検査し、循環を持つかどうか、つまり連続して cdr を取ることによってリストの終端を探そうとするプログラムが無限ループになるかどうかを判定する⼿続きを書け。

(define (has-loop x)
    (define mem '())
    (define (loop-check x)
        (cond 
            ((not (pair? x)) #f)
            ((memq (cdr x) mem) #t)
            (else
                (set! mem (cons (cdr x) mem))
                (loop-check (cdr x)))
    ))
(loop-check x))

(print (has-loop l3))
;#f
(print (has-loop l7))
;#f
(print (has-loop l_mevius))
;#t

cdrだけ辿っていって、自分自身のポインタを持つか探す