SICPを読む(53) 2.2.2(2) 木の写像

Scheme

さてさて、リスト処理も本格的な感じになってきます。今回は木の写像。

まずは普通に

ふつうに。

(define (scale-tree tree n)
  (cond ((null? tree) `())
        ((not-pair? tree) (* tree n))
        (else (cons (scale-tree (car tree) n)
                    (scale-tree (cdr tree) n)))))
(scale-tree '(1 (2 (3 4))) 10)
; (10 (20 (30 40)))

car,cdrで巡ればいい。

あ、not-pairはsrfi-1が必要。srfiを積極的に使っていこうと思います。

map再帰

ex-2.27 | SICP | OpenSource Webで出てきたmap再帰が登場。

こんなのは・・・。

(map (lambda (x) (+ x 10)) '(1 (2 (3 4))))
; Error

ダメだよね・・・。

仕方ないので、真面目に巡ろう。

(define (scale-tree tree n)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (scale-tree sub-tree n)
             (* sub-tree n)))
       tree))
(scale-tree '(1 (2 (3 4))) 10)
; (10 (20 (30 40)))

mapをして、pairを見ると。

map再帰セクシーすぎる!!

問題 2.30

square-treeを定義せよと。

ふつうの。

(define (square-tree tree)
  (cond ((null? tree) '())(list '())
        ((not-pair? tree) (square tree))
        (else
          (cons (square-tree (car tree))
                (square-tree (cdr tree))))))

map再帰。

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

map再帰の方がらくちん。

問題 2.31

tree-mapを定義せよ。

(define (tree-map f tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (tree-map f sub-tree)
             (f sub-tree)))
       tree))

使ってみる。

(define (square-tree tree) square tree)

(square-tree '(1 (2 (3 4) (5 6))))

スゲー楽。

問題 2.32

穴埋めながら全然わからず・・・。

とりあえず(subsets '(1 2))の場合の方針を練ってみる。

(append (list '()) (list '(2)) (list '(1) (list '(1 2))))
; (() (2) (1) ((1 2)))

あぁ、こんな感じか。(list '())を使っている理由が判明。

carを使ってないので、carを使えばなんとかなるような気がして、適当に・・・。

(define (subsets s)
  (if (null? s)
      (list '())
      (let ((rest (subsets (cdr s))))
        (append rest (map
                       (lambda (x) (cons (car s) x)) ; 穴の部分
                       rest)))))

えい!

(subsets '(1 2 3))
; (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

出来た!!

が、「明快に説明せよ」という問には答えられず・・・。

素晴らしい回答が
SICP memo: 問題2.32

地道にdisplayしてみた。

rest                 (cons (car s) x)
(())               + (3)
(() (3))           + (2) + (2 3)
(() (3) (2) (2 3)) + (1) + (1 3) + (1 2) + (1 2 3)
= (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

おぉ、わかった!!

ズズーっと下っていって。(list '())からスタートする。
restが、(())で、(())に3を加えると((3))。appendして(() (3))
(() (3))にそれぞれ2を加えると((2) (2 3))。appendして(() (3) (2) (2 3))
(() (3) (2) (2 3))にそれぞれ1を加えて、((1) (1 3) (1 2) (1 2 3))。appendしたら!!
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

つまり、

すべての部分集合の集合 ＝（「s の最初の要素」を含む部分集合の集合）
　　　　　　　　　　　 ＋（「s の最初の要素」を含まない部分集合の集合）

である。

できたぁぁぁっっっっっっっっっっっっっっ!!

Gaucheのライブラリが凄すぎ

Gauche リファレンスマニュアル: 組み合わせ
ナンダコレハ。