3.3.1 可変リスト構造 - yukichanko's diary

久々にSICP Lite#13 http://atnd.org/events/3505 に行ってきたので、復習を兼ねて、3.3.1からやってみま〜す。
方針は、例によって「難しい問題は飛ばすwww 」と言うもの。まぁ、Liteクラスタですから。

ここでは、リストを変更する、と言うことで、純粋関数型言語からどんどん外れていくところですね。
set-car!, set-cdr!などが登場します。今まで、構成子(Constructor)を作っていたのですが、時間によって変わるオブジェクトを表現するために、時変と言う概念が登場します。そのため、変更子(Mutator)なるものが登場します。

問題3.12

いきなり省略w

問題3.13

循環リストですね。

(last-pair (make-cycle '(a b c)))

を実行すると、リストを下っていきますが、永遠にNULLポインタにぶつからないので、無限ループに落ちる、と。

問題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 '()))

一旦、tempにxのcdr要素を保管しといて、xのcdrをyに付け替えている。
とりあえず、変数をトレースしてみる。

初期状態
x: a b c d
y: null
(loop x '())を実行
temp: b c d
x: a
(loop temp x)を実行
temp: c d
x: b a
(loop temp x)を実行
temp: d
x: c b a
(loop temp x)を実行
temp:
x: d c b a

と言う感じで、xは逆順になる。

何で有用なのかは、おそらくこんな手続きを少し後で使うことになるのだろう。

問題3.15

とりあえず、ポインタ図を書いてみた。

面倒なので、もう書かないw

問題3.16

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

これは、面白いなぁ。

3つと表示されるのは、普通の直列リスト。

(define x '(a b c))

4つと表示されるは、一つのオブジェクトを共有しているようなリスト

(define x '((b a) a))

何も表示されないのは、無限ループのリスト

7つと表示されるのは。。。すみません。わかりませんでした。
参考サイト: http://www.serendip.ws/archives/1285

なるほど〜。

問題3.17

ヒントの通りに実装したらいいみたい。
(ヒント: どの対が既に数えられたかを覚えておくのに使う補助データ構造を補正しながら構造を渡り歩け)

と言うことで、一つ可変リストを用意してやって、そこに数えたモノをどんどん追加して行く。
今、読んでいるものが、すでに読んでいるかどうかをそのリストと照合し、あればゼロを返し、なければカウントして行く。

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