SICP独習会 階層構造(問題2.24〜)

SICP


この節では、リストを使って木構造を表現しています。ここから、込みいったリストの使い方をしてくるので、リストについて理解しておかないと、キツくなってきます。(←私)

問題2.14

パッと頭の中に、図が浮かばない。list手続きの生成規則がわかってないんだなあ。

箱とポインタ構造

問題2.15

理解をしやすくするために、コマンドライン上で辿っていく様子と、「箱とポインタ構造」の2種類で表現しています。

一つめのリスト



gosh> (define x (list 1 3 (list 5 7) 9))

gosh> (cdr x)

(3 (5 7) 9)

gosh> (cdr (cdr x))

((5 7) 9)

gosh> (car (cdr (cdr x)))

(5 7)

gosh> (cdr (car (cdr (cdr x))))

(7)

gosh> (car (cdr (car (cdr (cdr x)))))

7

箱とポインタ構造

二つめのリスト



gosh> (define c (list (list 7)))

gosh> (car c)

(7)

gosh> (car (car c))

7

箱とポインタ構造

三つめのリスト



gosh> (define b (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))

gosh> (car (cdr b))

(2 (3 (4 (5 (6 7)))))

gosh> (cdr (car (cdr b)))

((3 (4 (5 (6 7)))))

gosh> (car (cdr (car (cdr b))))

(3 (4 (5 (6 7))))

gosh> (cdr (car (cdr (car (cdr b)))))

((4 (5 (6 7))))

gosh> (car (cdr (car (cdr (car (cdr b))))))

(4 (5 (6 7)))

gosh> (cdr (car (cdr (car (cdr (car (cdr b)))))))

((5 (6 7)))

gosh> (car (cdr (car (cdr (car (cdr (car (cdr b))))))))

(5 (6 7))

gosh> (cdr (car (cdr (car (cdr (car (cdr (car (cdr b)))))))))

\((6 7)\)

gosh> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr b))))))))))

(6 7)

gosh> (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr b)))))))))))

(7)

gosh> (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr b))))))))))))

7

箱とポインタ構造

なんとなリストの生成規則が掴めてきたかな？

問題2.26

定義



gosh> (define x (list 1 2 3))

x

gosh> (define y (list 4 5 6))

y

箱とポインタ構造

appendで繋いでみる



gosh> (append x y)

(1 2 3 4 5 6)

箱とポインタ構造

consで繋いでみる



gosh> (cons x y)

((1 2 3) 4 5 6)

箱とポインタ構造

listで繋いでみる



gosh> (list x y)

((1 2 3) (4 5 6))

箱とポインタ構造


なるほど。当たり前なことだけれども、consは「ただ組み合わせるだけ」、listは「並びを生成する」ということが、視覚化することによってはっきりとわかった。

問題2.27

ぐぬぬ。前に作ったお手製のreverse手続きは、要素数を利用して逆順にしていた。しかし、今回の木構造がからんでくると、要素数では木の深さが表現できないため、前回作ったreverseは利用できないんじゃないかと思った。なので、id:higeponさんreverse手続きを利用させてもらって定義しようと思った。が、たちまち3時間の立ち往生。解答を見ることに。

(define (deep-reverse lst)
  (if (null? lst)
    '()
    (append (deep-reverse (cdr lst))
            (if (pair? (car lst))
              (list (deep-reverse (car lst)))
              (list (car lst))))))
関数型言語の勉強にSICPを読もう - (11) 2章 - データによる抽象の構築(62-63ページ) - higepon blog

これは、わかりやすい。基本的な流れとして、どんどん後ろからリストをappendしていって、car部分も木構造であれば、遡っていくという感じか。で、以下が解答集の解答。

(define (deep-reverse tree)
  (if (not (pair? tree))
    tree
    (reverse (map deep-reverse tree))))
http://oss.timedia.co.jp/show/SICP/ex-2.27

これは、すごい。将太の寿司の柏手の安ならば、柏手の一発でもうってるぐらいスゴい。渡された要素が空リストではない限り、各木に対してreverseを作用させている。わかりずらいけど、図にしてみるとこうなった。



こんなエレガントなコードが早く(かつ速く)書けるようになるのは、いつになるだろうか。