Edited at

SICP読書録 #24 2.2.2(続き) 木に対するマップ - 練習問題 2.32

hiroshi-manabe様の日本語訳を使わせてもらいます。

練習問題等はGaucheで実行。

前回はこちら


木に対するマップ

木の全ての葉を掛け算する手続きscale-treeを作る。


_.scm

(define (scale-tree tree factor)

(cond ((null? tree) nil)
((not (pair? tree)) (* tree factor))
(else (cons (scale-tree (car tree) factor)
(scale-tree (cdr tree) factor)))))

動かしてみる。


_.scm

gosh> (scale-tree `(1 (2 (3 4) 5) (6 7)) 10)

(10 (20 (30 40) 50) (60 70))

同じ動作の手続きを、mapを使って定義してみよう。


_.scm

(define (scale-tree tree factor)

(map (lambda (sub-tree)
(if (pair? sub-tree)
(scale-tree sub-tree factor)
(* sub-tree factor)))
tree))


練習問題 2.30

全ての葉を2乗する手続きを作る。


_.scm

(define (square-tree tree)

(cond ((null? tree) nil)
((not (pair? tree)) (* tree tree))
(else (cons (square-tree (car tree))
(square-tree (cdr tree))))))

mapを利用する版も。


_.scm

(define (square-tree tree)

(map (lambda (sub-tree)
(if (pair? sub-tree)
(square-tree sub-tree)
(square sub-tree)))
tree))


練習問題 2.31

これまでの、mapを使った手続きは同じ構造をしている。抽象化できそうだ。


_.scm

(define (tree-map proc tree)

(map (lambda (sub-tree)
(if (pair? sub-tree)
(tree-map proc sub-tree)
(proc sub-tree)))
tree))

このtree-mapを使えば、square-treescale-treeは以下のように定義できる。


_.scm

(define (square-tree tree) (tree-map square tree))

(define (scale-tree tree factor)
(tree-map (lambda (x) (* x factor)) tree))


練習問題 2.32

集合を渡すと、全ての部分集合の集合を返す手続を作ろう。


_.scm

(define (subsets s)

(if (null? s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (x) (cons (car s) x)) rest)))))

実行結果。


_.scm

gosh> (subsets `(1 2 3))

(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

なぜこれでうまくいくのか?

$(x_1,...x_n)$の部分集合の集合は、$(x_1,...x_{n-1})$の部分集合と、同部分集合にそれぞれ$x_n$を追加した集合の和だから。

例えば・・・

(2 3)の部分集合は、(() (3) (2) (2 3))

(1 2 3)の部分集合は、(() (3) (2) (2 3))と、

これにそれぞれ1を追加した((1) (1 3) (1 2) (1 2 3))の和、になる。