SICPを読む(50) 2.2.2(1) 階層構造

階層構造になったら、想像力が追い付かなくなってきた・・・。

ふたつのリストの違い

(cons (list 1 2) (list 3 4)) ; ((1 2) 3 4)
(list (list 1 2) (list 3 4)) ; ((1 2) (3 4))

あれ?何が違うんだ!?

展開してみよう。

(cons (cons 1
            (cons 2
                  `()))
      (cons 3
            (cons 4
                  `())))

(cons (cons 1
            (cons 2
                  `()))
      (cons (cons 3
                  (cons 4
                        `()))
            `()))

consは横に並ぶ。

リストは階段状になる。

図2.5を作ってみる。

(cons (list 1 2) (list 3 4))

[ | ] -------- [ | ] - [ |/]
 |              |       |
[ | ] - [ |/]   3       4
 |       |    
 1       2
(list (list 1 2) (list 3 4))

[ | ] -------- [ |/]
 |              |
[ | ] - [ |/]  [ | ] - [ |/]
 |       |      |       |
 1       2      3       4

ポインタ記法を使うとリストは横に並ぶ。

ってことは、

(cons (list 1 2) (list 3 4))
; ((1 2) 3 4)

は、

(list (list 1 2) 3 4)
; ((1 2) 3 4)

と書き直すことができる。


おぉぉぉ!!理解できた!!

やはり手を動かすと理解できる。

count-leaves

ツリーを巡る方法。

(define (count-leaves x)
  (cond ((null? x) 0)
        ((not (pair? x)) 1)
        (else (+ (count-leaves (car x))
                 (count-leaves (cdr x))))))

(not (pair? x))で、ペアでは無い → atomである → 一個足す

慣用句として頭に叩き込んでおこう。

まとめ

多次元配列も、ツリーもみんなリストで表現出来てしまう。リストは強力な武器になりそうだ。