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である → 一個足す
慣用句として頭に叩き込んでおこう。
まとめ
多次元配列も、ツリーもみんなリストで表現出来てしまう。リストは強力な武器になりそうだ。