SICP 読書ノート#7 - 2.2 階層データ構造と閉包性 (pp.55-65)
「§2.2 階層データ構造と閉包性」から。
閉包性とはclosure propertyというそうだが、このclosureはJavaScripter等で おなじみの「クロージャ」ではなく、部品(モジュール同士)が密結合することなく 部品のプロパティがその中に閉じており独立性が保たれている状態を指す模様。
並びの表現
(list <a1> <a2> ... <an>)
と
(cons <a1> (cons <a2> ... (cons <an> nil) ... ))
は等価。
それ以外のリスト演算も写経しておく。
(define (list-ref items n) (if (= n 0) (car items) (list-ref (cdr items) (- n 1)))) (define squares (map square (range 1 6))) (list-ref squares 3) ;; => 16 (define (length items) (if (null? items) 0 (+ 1 (length (cdr items))))) (define odds (filter odd? (range 1 8))) (length odds) ;; => 4 ;;; lengthの反復プロセス版 (define (length-iter items) (define (iter rest count) (if (null? rest) count (iter (cdr rest) (+ 1 count)))) (iter items 0)) ;;; append ;;; リストをcdrダウンしつつconsアップ (define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2)))) (append squares odds) ;; => '(1 4 9 16 1 3 5 7)
問題 2.17
リストをcdrダウンして最後のpair(cons)を返す。
(define (last-pair lst) (cond ((null? lst) nil) ((null? (cdr lst)) (car lst)) (else (last-pair (cdr lst)))))
問題 2.18
リストを反転させる。cdrダウンしながらconsアップ。
(define (reverse lst) (define (iter lst result) (if (null? lst) result (iter (cdr lst) (cons (car lst) result)))) (iter lst nil))
階層構造
consまたはlist、またはそれらを組み合わせて木などのデータ構造を構築したり操作したり。
問題 2.26
append, cons, list の振る舞いを確認。ポインタ図は割愛。（手元のノートには書いたけど..）
racket@> (define x (list 1 2 3)) racket@> (define y (list 4 5 6)) racket@> (append x y) '(1 2 3 4 5 6) racket@> (cons x y) '((1 2 3) 4 5 6) racket@> (list x y) '((1 2 3) (4 5 6))
問題 2.27
木に対応したreverse手続き。carの要素がリストの場合はさらに再帰呼び出しで展開する
(define (deep-reverse tree) (define (iter tree result) (cond ((null? tree) result) ((pair? (car tree)) (iter (cdr tree) (cons (deep-reverse (car tree)) result))) (else (iter (cdr tree) (cons (car tree) result))))) (iter tree nil))
(2014/7/7 追記) reverseとmapを使えばもっと簡潔に書けるらしい。なにこれすごい。
(define (deep-reverse tree) (if (not (pair? tree)) tree (reverse (map deep-reverse tree))))
問題 2.28
木をフラットにする手続き。
(define (fringe tree) (define (iter tree result) (cond ((null? tree) result) ((pair? (car tree)) (iter (cdr tree) (append result (fringe (car tree))))) (else (iter (cdr tree) (append result (list (car tree))))))) (iter tree nil))
問題 2.29
Binary Mobileの問題。やってみたら色々手こずって１時間くらいかかってしまった…
Binary Mobileとは左右の枝におもりまたは子mobileがぶら下がっていて、 それらの左右のバランスが取れているものらしい。インテリアショップとかで たまに天井からぶら下がっているあれ。
コンストラクタはテキストから与えられる。
(define (make-mobile left right) (list left right)) (define (make-branch length structure) (list length structure))
a.
左右の枝(branch)および、枝の長さ(length)、 おもりまたはモービル(structure)のアクセサを実装する。
(define (left-branch mobile) (car mobile)) (define (right-branch mobile) (cadr mobile)) (define (branch-length branch) (car branch)) (define (branch-structure branch) (cadr branch))
テスト。
(define m (make-mobile (make-branch 3 (make-mobile (make-branch 3 1) (make-branch 1 3))) (make-branch 4 (make-mobile (make-branch 1 2) (make-branch 2 1))))) (left-branch m) ;; => '(3 ((3 1) (1 3))) (branch-length (left-branch m)) ;; => 3 (branch-structure (left-branch m)) ;; => '((3 1) (1 3)) (right-branch m) ;; => '(4 ((1 2) (2 1))) (branch-length (right-branch m)) ;; => 4 (branch-structure (right-branch m)) ;; => '((1 2) (2 1))
b.
モービルの重量を求める手続きを実装する。
; 錘であればtrue、モービルであればfalse (define (simple-weight? branch) (not (pair? (branch-structure branch)))) (define (total-weight mobile) (cond ((atom? mobile) mobile) ((simple-weight? mobile) (branch-structure mobile)) (else (+ (total-weight (branch-structure (left-branch mobile))) (total-weight (branch-structure (right-branch mobile)))))))
テスト。
(total-weight (make-branch 1 3)) ;; => 3 (total-weight m) ;; => 7
c.
モービルが釣り合っているかどうかをチェックする手続き。 左右が釣り合っているかどうかの判定は、モーメントが等しいかで行う。
(define (moment branch) (* (branch-length branch) (total-weight (branch-structure branch)))) (define (balanced? mobile) (cond ((atom? mobile) #t) ((simple-weight? mobile) #t) (else (let* ((l (left-branch mobile)) (r (right-branch mobile))) (and (= (moment l) (moment r)) (balanced? (branch-structure l)) (balanced? (branch-structure r)))))))
テスト。
(moment (make-branch 1 3)) ;; => 3 (moment (left-branch m)) ;; => 12 (balanced? (make-branch 1 3)) ;; => true (balanced? m) ;; => true
d.
コンストラクタのデータ構成をlistからconsに置き換えた場合、 既存のコードはどの程度変更しなければならないか？
(define (make-mobile left right) (cons left right)) (define (make-branch length structure) (cons length structure))
もちろんアクセサを変更するだけでよい。
(define (left-branch mobile) (car mobile)) (define (right-branch mobile) (cdr mobile)) (define (branch-length branch) (car branch)) (define (branch-structure branch) (cdr branch))
ただし、前述のmのように構築済みのデータオブジェクトは、評価して再度構築し直すこと。 （ここでやたらはまる…）
問題 2.30
木の要素を全て二乗する手続き。
(define (square-tree tree) (cond ((null? tree) tree) ((not (pair? tree)) (square tree)) (else (cons (square-tree (car tree)) (square-tree (cdr tree))))))
問題 2.31
木の全ての要素に手続きを適用する tree-map を実装し、 square-treeもそれを利用する。
(define (square-tree tree) (tree-map square tree)) (define (tree-map proc tree) (cond ((null? tree) tree) ((not (pair? tree)) (proc tree)) (else (cons (tree-map proc (car tree)) (tree-map proc (cdr tree))))))
問題 2.32
集合のすべての部分集合は、任意の要素とそれ以外の要素の組み合わせで作成できる。 よくわかってないけどそんな感じ？
;; <??> は (lambda (x) (cons (car s) x)) (define (subsets s) (if (null? s) (list nil) (let ((rest (subsets (cdr s)))) (append rest (map (lambda (x) (cons (car s) x)) rest)))))
次回は「§2.2.3 公認インターフェースの並び」から。
