3.3.1 可変リスト構造
久々に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.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)