SICP 読み (22)
問題 2.29 の検討で一日ハマッたのでスルーに決定。
問題 2.30
解のみ。
(define (square-tree l)
(cond ((null? l) '())
((not (pair? l)) (* l l))
(else
(cons (square-tree (car l))
(square-tree (cdr l))))))
(define (square-tree l)
(map (lambda (sub-tree)
(if (pair? sub-tree)
(square-tree sub-tree)
(* sub-tree sub-tree)))
l))
問題 2.31
これも解のみ。
(define (square x) (* x x))
(define (square-tree tree) (tree-map square tree))
(define (tree-map f l)
(map (lambda (x)
(if (pair? x)
(tree-map f x)
(f x)))
l))
問題 2.32
subsets に (cdr s) を渡してどうして先頭要素が (以下略
例えば以下だと。
(define (subsets s)
(define (f x)
'()
)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map f rest))))
)こうなった。
gosh> (subsets '(1 2 3)) (() () () () () () () ()) gosh>
何故だ。(それにしてもコードが微妙スギ
では、ということで以下。
(define (subsets s)
(define (f x)
; '()
)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map f rest))))
)実行したらどうなるか。
gosh> (subsets '(1 2 3)) (() #<undef> #<undef> #<undef> #<undef> #<undef> #<undef> #<undef>) gosh>
と、ゆー事は '(1 2 3) を渡した場合は map の中の f は七回呼ばれてるんだな。何故だ。
置き換えしてみようか。
(subsets '(1 2 3)) (subsets '(2 3)) (subsets '(3)) (subsets '()) (append (list '()) (map f '())) (append (list '()) '()) (append (append (list '()) '()) (map f (append (list '()) '()))) (append (()) (map f (()))) (append (()) (())) (append (append '(()) '(())) (map f (append '(()) '(())))) (append '(() ()) '(() ())) (append (append '(() ()) '(() ())) (map f (append '(() ()) '(() ())))) (() () () () () () () ())
cdr でカワを剥いでいって、空リストを皮切りに倍々になっている。不思議な事に部分集合の要素数と合致しているのが分かる。
で、なんか分かりにくいけど、f を別な手続きにしちゃダメな感じがする。map には lambda 式を渡さないと s が使えんぞ。こうしてみたらどうなるか。
(define (subsets s)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map
(lambda (x)
(list (car s))
)
rest))))
)を。出力は以下。
gosh> (subsets '(1 2 3)) (() (3) (2) (2) (1) (1) (1) (1)) gosh>
これはなかなかいい調子のような気が。ってーかそれぞれの s の状態が見たひ。
置き換え使って机上で検証してみるか。
(subsets '(1 2 3)) (subsets '(2 3)) (subsets '(3)) (subsets '()) (append '(()) (map (lambda (x) (list (car s))) '(()))) ;; s => (3) (append '(()) (cons (list (car '(3))) '()) (append '(()) '((3))) (append '(() (3)) (map (lambda (x) (list (car s))) '(() (3)))) ;; s => (2 3) (append '(() (3)) (cons (list (car s)) (cons (list (car s)) '()))) (append '(() (3)) '((2)) '((2))) (append '(() (3) (2) (2)) (map (lambda (x) (list (car s))) '(() (3) (2) (2)))) -以下略-
上記によれば (()) なリストに (car '(3)) と '() が cons されたリストを追加すれば OK で、(() (3)) なリストには
- (car '(2)) と '()
- (car '(2)) と (car '(3))
を追加すれば OK か。この結果、(() (3) (2) (2 3)) ができる。
さらにこのリストに map の引数 '(() (3) (2) (2 3)) と (car '(1)) の組み合わせを追加すれば OK な感じ。それは分かっていたのですが結構悩んだ。
挙句にヒリ出したのが以下。
(define (subsets s)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map
(lambda (x)
(cons (car s)
(if (null? x)
'()
(cons (car x) '()))
)
)
rest))))
)惜しい。
gosh> (subsets '(1 2 3)) (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2)) gosh>
省略してますが微妙な出力をたくさん見た。で、x はリストなので car じゃ駄目だ、とゆー事で色々試す内に map を使えばいいんじゃん、という事にようやく気がつく。
(define (subsets s)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map
(lambda (x) (cons (car s) (map (lambda (x) x) x)))
rest))))
)やったぁ。
gosh> (subsets '(1 2 3)) (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)) gosh>
それは良いが「明快に説明」ってどうしたものか。とりあえずもう少し時間を下さひ。
