2.2.2 階層構造

SICP

この辺り苦手なとこ。

問題2.24

実行例

(list 1 (list 2 (list 3 4)))
=> (1 (2 (3 4)))

ポインタ絵

ツリー絵

問題2.25
(1 3 (5 7) 9) 
(cadr (car (cddr x)))

((7))
(car (car x))

(1 (2 (3 (4 (5 (6 7))))))
(cadr (cadr (cadr (cadr (cadr (cadr x))))))
問題2.26
(append x y)
=> (1 2 3 4 5 6)
(cons x y)
=> ((1 2 3) 4 5 6)
(list x y)
=> ((1 2 3) (4 5 6))

絵にしてみた。

問題2.27
(define (deep-reverse items)
  (define (iter a b)
	(cond ((null? b) a)
		  ((pair? (car b)) 
		   (iter (cons (deep-reverse (car b)) a) (cdr b)))
		  (else 
		   (iter (cons (car b) a) (cdr b)))))
  (iter '() items))
問題2.28

答えを見てしまったorz

(define (fringe items)
  (cond ((null? items) '())
   	     ((not (pair? items)) (list items))
	     (else (append (fringe (car items))
		    		      (fringe (cdr items))))))

appendでくっつければいいんだろうけど、ソロのitemsをどうやって返せばいいんだっけ。。。と言うところでパニクりました。

問題2.29

めんどっちぃ。

  • aの問題
(define (make-mobile left right)
  (list left right))
(define (make-branch length structure)
  (list 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))
  • bの問題
(define (total-weight mobile)
  (let ((left  (left-branch mobile))
		(right (right-branch mobile)))
	(+ (add-weight left)
	   (add-weight right))))
(define (add-weight branch)
  (let ((structure (branch-structure branch)))
	(cond ((pair? structure) (total-weight structure))
		  (else structure))))

テスト

gosh> (define abc '((5 ((3 2) (2 3))) (2 10)))
gosh> (total-weight abc)
15

ま、合ってるかな。

  • cの問題
(define (balanced? mobile)
  (let ((left  (left-branch mobile))
		(right (right-branch mobile)))
	(= (length-weight left)
	   (length-weight right))))
(define (length-weight branch)
  (let ((length (branch-length branch))
		(structure (branch-structure branch)))
	(cond ((pair? structure)
		   (* length (total-weight structure)))
		  (else (* length structure)))))

合ってるつもり。

問題2.30
  • No map版
(define (square-tree tree)
  (cond ((null? tree) '())
	     ((not (pair? tree)) (square tree))
	     (else (cons (square-tree (car tree))
				 (square-tree (cdr tree))))))
  • map版
(define (square-tree-map tree)
  (map (lambda (sub-tree)
              (if (pair? sub-tree)
		   (square-tree-map sub-tree)
		   ((lambda (x) (* x x)) sub-tree)))
	   tree))
問題2.31
(define (tree-map op tree)
  (map (lambda (sub-tree)
	      (if (pair? sub-tree)
		   (tree-map op sub-tree)
		   (op sub-tree)))
	   tree))
(define (square-tree tree) (tree-map square tree))
問題2.32

この問題、ぼくの脳では解釈不能。

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

いろんな方

この場を借りて、Thanksです。

かなり言葉足らずのところがあったと思うのだけど(ベキ乗は一応理解してますよ^^; 今までに何度か書いているので)、ぼくが知りたかったのは、どうやったら

(let ((rest (subsets (cdr s))))
  ...

と言うようなコードが思い浮かぶのかなぁ。。。と言うこと。

letを使わずに書くと理解できたのだけど、

(define (subsets s)
  (define (append-top rest)
	(append rest
			(map (lambda (x) (cons (car s) x))
				 rest)))
  (if (null? s)
	  (list s)
	  (begin 
		(append-top (subsets (cdr s))))))

ここから、例のlet付きに至る思考プロセスと言うのが、Lisp脳な人たちはどうなっているんだろう、と言うのが知りたかった点です。

この問題だけに限らず、Lisperの人たちが書くコードを見ると、脳の違う部分が動いているのかなぁ。。。と感じます。
さらに、そんな人がごく一握りの特殊な人ってわけじゃなく、結構身近にいるので、さらに驚かされます。