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

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

_.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-treeとscale-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))の和、になる。