SICP独習会 階層構造その２(問題2.28〜）

長くなってしまったので、分けて掲載することにしました。

問題2.28

だんだん何がわからないかがはっきりしてきた。私がわからないのは、「どうやってすべての葉にアクセスするか」ということだと思う。で、例のcount-leavesを参考にここまではできた。

(define (fringe tree)
  (let ((ret '()))
    (cond
      ; if empty list
      ((null? tree) '())
      ; if leaf
      ((not (pair? tree)) tree)
      ; if branch
      (else (append)))))

どのようにappendすればよいか、わからなかった。で解答の解答を見てみた。

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

http://oss.timedia.co.jp/show/SICP/ex-2.28

うーむ。carやcdrでfringeした返り値が、リストというのが今一想像できない。どうしたものか。

ここでもう一度、何が良くわかっていないのか整理してみる。

• pari?、null?で返されるものはなにか

ということなんじゃないかな。

なので色々調べてみたら、このような表を見つけた。

述語	ドット対(1 . 2)	空リスト	空でないリスト
pair?	#t	#f	#t
list?	#f	#t	#t

http://karetta.jp/book-node/gauche-hacks/008223

ふむ。これから(not (pair? ~))は、(null? ~)と等価ということになるな。でもあえて、別々に処理してるのは、空リストと、要素を分けて処理したいからということである。この認識自体は間違っていないようだ。

ここでtraceのことを思いだして、traceでfringeの動きを追ってみることにした。以下がその出力。

gosh> (fringe (list (list 1 2) (list 3 4)))

CALL fringe ((1 2) (3 4))

 CALL fringe (1 2)

  CALL fringe 1

  RETN fringe (1)

  CALL fringe (2)

   CALL fringe 2

   RETN fringe (2)

   CALL fringe ()

   RETN fringe ()

  RETN fringe (2)

 RETN fringe (1 2)

 CALL fringe ((3 4))

  CALL fringe (3 4)

   CALL fringe 3

   RETN fringe (3)

   CALL fringe (4)

    CALL fringe 4

    RETN fringe (4)

    CALL fringe ()

    RETN fringe ()

   RETN fringe (4)

  RETN fringe (3 4)

  CALL fringe ()

  RETN fringe ()

 RETN fringe (3 4)

RETN fringe (1 2 3 4)

(1 2 3 4)

うーむ。葉の部分にアクセスした時に返されるのは、fringeを呼ぶ時の引数が、普通の値の時、返される値が既にリストになっているのがわからない。うーむ。

問題2.29

最初、

//うごきません
(define (total-weight x)
  (cond ((null? x) 0)
        ; if branch
        ((pair? x)
         (if (pair? (branch
        ; if mobile
        (else (+ (total-weight (left-branch x))
                 (total-weight (right-branch x))))))

というようなコードを書いた。しかし、brancheもmobileもともにリストのため、どうやって場合分けするのか思い付かなかった。そこで、またまた解答集のお世話に。

(define (total-weight mobile)
  (let ((left (left-branch mobile))
        (right (right-branch mobile)))
    (+ (branch-weight left)
       (branch-weight right))))

(define (branch-weight branch)
  (let ((structure (branch-structure branch)))
    (if (not (pair? structure))
        structure
        (total-weight structure))))

http://oss.timedia.co.jp/show/SICP/ex-2.29

なるほど。手続きを二つに分けている。無理に一つの手続きでやる必要はなかったんだな。これが2パスで問題を解くということなのか。あと始点は必ずmobileなので、branchかどうかを判断する必要もない訳だ。