Hatena::Groupsicp

SICP読書メモ

|

2009-02-02

3.4.1 16:13

MuhamadMuhamad2012/10/06 10:42The purhcsaes I make are entirely based on these articles.

nfioggqyanfioggqya2012/10/07 00:10FCDp7R <a href="http://dzuafetmtyoi.com/">dzuafetmtyoi</a>

tqdxzsazsxptqdxzsazsxp2012/10/08 03:09KP5Bf2 , [url=http://savvkicdrabd.com/]savvkicdrabd[/url], [link=http://lfsbupxhenss.com/]lfsbupxhenss[/link], http://bgoesktscaff.com/

vqtuxgnauovqtuxgnauo2012/10/08 17:02KbLbVE <a href="http://ogukeaerunqa.com/">ogukeaerunqa</a>

ddtqufwqddtqufwq2012/10/09 04:16JFmebK , [url=http://oddeuqwujehu.com/]oddeuqwujehu[/url], [link=http://nycerlxqkiqq.com/]nycerlxqkiqq[/link], http://dgqtvjdjxfxy.com/

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20090202

2009-02-01

3.3.3 表の表現 23:56

表はkeyとvalueの対のリストとして表現できる。

 [].[]----[].[]----[].[]----[].[]----[]
  |        |        |        |
 *table*   |        |        |
          [a].[1]  [b].[2]  [c].[3]

lookup はリストを走査し、一致するkeyを探しその対を返す.

insert! はその対に対し (set-cdr! pair new-value) を実行する.

(無ければ新しく作る)

ここでset-cdr!が無いとinert!で再代入ができない。


3.3.2 キューの表現 23:56

set-car! と set-cdr! を利用してキューをする。

まず、実際のデータを保持する単純なリストとしてキューを表現した場合

キューから先頭のデータを取得するのは

(define (front-ptr queue)
  (car queue))

で良い、挿入をするためにはリスト全体を操作して最後尾を見つける必要がある。

少し改良して、データリストの先頭と最後尾へのポインタを持つ対としてキューを表現する。

 [].[]-------------|
  |                |
  V                V
 [][]--> [][] --> [][] --> []
  |       |        |
  1       2        3

これで先頭と最後尾が判るので、それぞれの代入でpop・push等が表現できそう。


3.3.1 可変データでのモデル化 - 可変リスト構造 23:56

代入を導入したことで、計算オブジェクトが状態を持つようになった。

2章で扱った合成データオブジェクトの構成子・選択子に次いで、変更子を含んだデータ抽象を考える。


3.2.4 内部定義 23:56

環境は変数だけでなく、内部手続きも保持する。

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

上の例では、内部手続き improve はxを参照している

そのxは (sqrt 100) 等を評価した時作られる環境のxとなり、globalのxではない。

いわゆるクロージジャか、JavaScriptなんかでも結構多用する。


3.2.3 局所変数の入れ物としてのフレーム 23:56

set! を取り入れた当初の目的 make-withdraw に戻って、評価の環境モデルでどう動作するか考える。

(define (make-withdraw balance)
  (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds")))

を評価すると

---global-------------
|                    |
| make-withdraw -|   | <--------
----------|-----------         |
          |                    |
          O . O ---------> -> -|
          |
   パラメタ:balance
   -----------------
   (lambda (amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
               balance)
        "Insufficient funds"))

その上で (define tom (make-withdraw 1000)) を評価する

---global----------------
|                        |
| tom ---|               |
---------|----------------
         V           ^
         |           |
         |      | --- E1 ---------|
         |      | balance : 1000  |
         |      |-----------------|
         |               ^
         |               |
       O . O ---> --> -->|
       |
   パラメタ:amount
   ---------------
   (if (>= balance amount)
       (begin (set! balance (- balance amount))
               balance)
       "Insufficient funds")

tom は手続きに束縛され、その手続きは外部環境としてE1を指す。

E1は仮引数のbalanceに1000が束縛されている。

つまり、lambdaは環境を作り、その環境は局所変数の入れ物にすることができる。

実際schemeで局所変数をつくる let は lambda のシンタックスシュガーになっている。

(let ((x 100))
  (* x x))

;;は↓と等価

((lambda (x)
  (* x x))
 100)

3.2.2 単純な手続きの作用 23:56

実際に評価の環境モデルの詳細を見ていく。

(define (square x)
  (* x x))

(+ (square 5)
   (square 10))

を評価した時に、仮引数の x がバッティングしないのは

二つの(square *)でそれぞれ別の環境が作られ、それぞれの環境内で変数 x に 5 と 10 がそれぞれ束縛されているから。

なるほど。


3.2.1 評価の環境モデル - 評価の規則 23:56

代入を導入するために、評価の環境モデルを考える。

(define (square x)
  (* x x))

をglobal環境で評価すると

(define square
  (lambda (x) (* x x)))

となり、global環境の square という名前に (lambda (x) (* x x)) が束縛され

square手続きはglobal環境へのポインタを持つ。

(未定義の変数が評価された場合、親の環境を探す)

手続きは、本文 (lambda (x) (* x x))) と外部環境へのポインタの対で表現できる。

---global------
|             |
| square -|   | <---------------
----------|----                |
          |                    |
          O . O ---------> -> -|
          |
    (lambda (x) (* x x)))

(square 5) を実行した場合。新しいフレームが作られ

そのフレーム内で、引数が x に束縛され、外部環境としてglobal環境へのポインタをつ.

---global------
|             |
| square      |
---------------
          |
  | --- temp1 ----|
  |               |
  |  x : 5        | 変数テーブル
  |---------------|
  | (* x x)       | 手続き
  |---------------|

手続きを実行することは、引数が束縛された新しいフレームを作り

その中で手続きを評価する事になる。

確かに実際の処理系がやっていることに近づいてきた気がする。

Gaucheとか調べてみようかな、今度。

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20090201

2009-01-20

3.1.3 代入を取り入れたコスト 23:40

代入を取り入れることで、同じ手続きを同じ引数で実行した場合の結果が異なる場合が生まれる.

とすると単純な評価置き換えモデルで、手続きを評価できなくなり.参照透明性が破られる。

テストを複雑にする諸悪の権化だよな、確かに。

AndralynAndralyn2011/04/10 18:01bj1p7Y BION I'm impressed! Cool post!

exbxfhvmexbxfhvm2011/04/23 01:28vL9fOW <a href="http://uansxknsucvg.com/">uansxknsucvg</a>

lsczvmcilsczvmci2011/04/24 11:50hBORbB , [url=http://iqghoodnqadm.com/]iqghoodnqadm[/url], [link=http://rovgfdgyxple.com/]rovgfdgyxple[/link], http://ycscpvgwhvzb.com/

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20090120

2008-12-31

3.1.2 代入を取り入れた利点 23:40

代入を取り入れる事による利点を、乱数発生器の実装とそれを利用したモンテカルロシミュレーションの実装を通して見ていく。

乱数発生器の状態を、局所的変数への代入を利用して表現することで、乱数発生器とモンテカルロシミュレーションの手続きの実装を完全に分離することができ、さらにモンテカルロシミュレーションの実装とそれへ与える確率を求めるべき手続きの実装も分離し、各部品をモジュラーブルにすることができる。

逆に乱数発生器の状態を局所的変数への代入ではなく、繰り返し手続きへの仮引数として表現した場合、乱数発生器とモンテカルロシミュレーションの手続きが干渉し合う。またモンテカルロシミュレーションを汎用的なフレームワークとして仕立て上げることができない。

局所的変数への代入によって、オブジェクトの状態を表現することで、巨大で複雑なシステムをモジュラーブルでシンプルに実装できそう、な予感がする。がそのデメリットもあるよ、ということで次に続くみたい。

単純に思いつくデメリットとしては、手続きが状態を持つとテストのパターンが増えて複雑になって大変だ、という気がするけどどうだろ?

DarenceDarence2012/10/07 09:45This is crystal clear. Thanks for tkanig the time!

whpaxarchjmwhpaxarchjm2012/10/07 18:29c2j7xr <a href="http://lwuccbhmpuza.com/">lwuccbhmpuza</a>

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20081231

2008-12-21

3.1.1 代入と局所状態 00:15

状態を持ったオブジェクトを表現するための方法を見ていく。

  • global変数として状態変数を持つ
  • letで局所変数として作る
  • make-*** として仮引数を状態変数として使う手続きを返す
  • メッセージを受けて局所的な手続きを返す dispatch 手続きとしてオブジェクトを表現する

という順番で進んでいく。

途中の問題定義

『手続きに "状態" を持たせると、同じ関数引数の組み合わせでも呼ぶ度に結果が変化する』

が面白い。確かに複雑になっていく・・、というかテストがやり難いよなー。

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20081221

2008-12-07

2.5.2 異なる型の統合 - 強制型変換 00:15

続いて、異なる型の演算も実装したい。

まずシンプルに、有理数と整数の加算を add-rational-scheme-number として実装して

(put 'add '(rational scheme-number) add-rational-scheme-number)

(put 'add '(scheme-number rational) add-rational-scheme-number)

としても良い。ただそれだと型と演算子が増えると級数的に手続きが増えてきりがない。。

ということで、異なる型の場合は、型を変換し汎用の手続きで処理する。

型変換 -> 階層構造を持った型変換へ話が広がって、単純な階層ではない場合

その変換のために階層のネットワークを探索する必要がある、という問題が提示される。

あと、欄外の

「オブジェクト指向の複雑さはこの種の問題にある、この問題は計算機言語の範疇を越えて

 知識表現や自動推論の研究に頼る必要がある」

というのが面白かった。

YamaryYamary2011/04/11 01:39uPmrWY Home run! Great slugging with that answer!

jaboesfyjaboesfy2011/04/13 06:0525bdkw , [url=http://rerbncxjeuom.com/]rerbncxjeuom[/url], [link=http://axywsnuhzlmw.com/]axywsnuhzlmw[/link], http://pajeakuodlaw.com/

miclccjmoimiclccjmoi2011/04/23 02:344gG6ab <a href="http://fairgmcynqzr.com/">fairgmcynqzr</a>

cjrmprcjrmpr2011/04/24 11:474OX9MN , [url=http://cylviptuiasi.com/]cylviptuiasi[/url], [link=http://xgyrrpwrwbbq.com/]xgyrrpwrwbbq[/link], http://wcjixoayssrt.com/

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20081207

2008-12-06

2.5.1 汎用算術演算 22:44

整数/有理数/複素数 それぞれを抽象化した、汎用算術演算パッケージを作る。

データ主導アプローチで、データに型のタグを付け、そのタグに紐づく手続きを登録する。

手続きと型・オペレーション名の登録にはhash-tableを使った。

ChaimaeChaimae2012/10/06 16:12It's spokoy how clever some ppl are. Thanks!

rgzevstrgzevst2012/10/07 00:43xjmy2m <a href="http://bdpuqgvxrbww.com/">bdpuqgvxrbww</a>

sdvecsissdvecsis2012/10/10 01:44RnBPL8 , [url=http://eqywckxvcprh.com/]eqywckxvcprh[/url], [link=http://fdqjlsamodhi.com/]fdqjlsamodhi[/link], http://djkvsaoovaws.com/

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20081206

2008-12-02

2.4.2 タグ付きデータ 02:15

続いて、データオブジェクト直交座標形式か極座標形式か判断するために、型の'タグ'を付ける.

AdelphiaAdelphia2011/04/10 21:58FMKYDA That's a mold-breaker. Great thinking!

kvrycxljkvrycxlj2011/04/23 01:34g9PaLm <a href="http://bcdlxwpnxbws.com/">bcdlxwpnxbws</a>

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20081202

2008-12-01

2.4.1 複素数の表現 - 抽象データの複数表現:汎用手続き 00:43

あるデータを抽象的に表現する方法を色々と見てきた、その実装をデータの種類によって切り替える方法を2.4章では実践していくみたい。

具体的にはHuffman符号木の節で出てきたノードorリーフで振る舞いを変える手続き、みたいな。オブジェクト指向で言うポリモフィズムみたいな概念になるのかな。

アプローチとしては、データオブジェクト自体にその'型'を判別するタグを持たせ、それに応じ手続きを変えるらしい。

実際の例として複素数を表現していく。複素数・・・昔やったような、虚数だよね、くじけずに進もう。

今回の実装では二つの表現を行う、複素数を実数の軸と虚数の軸による平面上の点として表現する '直交座標形式' と 角度と距離として表現する '極座標形式'

もうこの辺でくじけそうだけど、、二つの方式を採用する理由として、加算の場合は '直交座標形式' が素直に表現でき、乗算の場合は '極座標形式' が素直に表現できる、らしい。。

なんとなくは理解できた、そのためデータオブジェクト '複素数' の外部インターフェイスとして、2種類のコンストラクタと4種類の選択子を実装する。

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20081201

2008-11-24

2.3.4 Huffman符号化木 02:26

リストによる木・集合の表現を発展させて、0と1のビット列を表現する。


ビット列の例、ASCIIコードの場合アルファベット数字128種類を、それぞれ7ビットのパターンで

符号化して表現する、固定長符号化という。対してモールス信号等は頻繁に利用する文字に短いパターンを割り当てて、結果的にデータ量の節約が工夫されている、可変長符号化。


可変長符号化は通信文に頻出するパターンに重み付けをして、頻出するフレーズに短いビット列のパターンを割り当てるのが肝、みたい。その可変長符号化の例としてHuffman符号化を見てみる。


二分木としてHuffman符号を表現すると
;;;(1) A = 4, B = 2, その他 = 1 の重みの場合
     /\
    /  \
   /   /\
  /   /  \
 /   B:2  \
A:4       /\
         /  \
       C:1  D:1

みたいな理解で正しいのかな。


そして木の左右を0と1で表現すれば、(1) の場合 'C' をビット例で 110 と表現でき

ビット列 10 を 'B' に、最も頻出する 'A' は 0 で表現できる。

Huffman木の生成

ここで


「手続きsymbolsとweightは、葉から呼び出されたか、一般の木から呼び出されたかにより

多少違うことをやらなければならない(振る舞いを変える)これは汎用手続きの例である」


とある。

オブジェクト指向なら、より汎用的・モジュール的にするために俄然ポリモフィズムを使う所だけど

関数指向言語の場合はどう解決するのが定石なんだろう?それは後、と書いてあるが気になりつつ続ける。


;;0は左の木、1は右の木
(define (choose-branch bit branch)
  (cond ((= bit 0) (left-branch branch))
        ((= bit 1) (right-branch branch))
        (else (error "bad bit -- CHOOSE-BRANCH" bit))))

;;ビット列を走査し結果をリストで返す。元になるHuffman符号化木を引数に渡す。
(define (decode bits tree)
  (define (decode-1 bits current-branch)
    (if (null? bits)
        '()
        (let ((next-branch
               (choose-branch (car bits) current-branch)))
          (if (leaf? next-branch)
              (cons (symbol-leaf next-branch)
                    (decode-1 (cdr bits) tree))
              (decode-1 (cdr bits) next-branch)))))
  (decode-1 bits tree))


(decode '(0 1 0 0 1 0 0 1 1 0 0 1 1 1)
        (make-tree
         (make-leaf 'a 4)
         (make-tree
          (make-leaf 'b 2)
          (make-tree
           (make-leaf 'c 1)
           (make-leaf 'd 1)))))
;;;(a b a b a c a d)

葉の重みでソートした集合を作る


(define (adjoin-set x set)
  (cond ((null? set) (list x))
        ((< (weight x) (weight (car set))) (cons x set))
        (else (cons (car set)
                    (adjoin-set x (cdr set))))))

(define (make-leaf-set pairs)
  (if (null? pairs)
      '()
      (let ((pair (car pairs)))
        (adjoin-set (make-leaf (car pair)
                               (cadr pair))
                    (make-leaf-set (cdr pairs))))))

(make-leaf-set '((a 4) (b 1) (c 9) (d 3)))
;;;((leaf b 1) (leaf d 3) (leaf a 4) (leaf c 9))

問2.67 サンプルの木で復号化を試す


(define sample-tree
  (make-code-tree (make-leaf 'A 4)
                  (make-code-tree
                   (make-leaf 'B 2)
                   (make-code-tree (make-leaf 'D 1)
                                   (make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

(decode sample-message sample-tree)
;;;(A D A B B C A)

問2.68 encode - メッセージとHuffman符号化木からビット例を生成する


(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

(define (contain? symbol list)
  (cond ((null? list) #f)
        ((eq? symbol (car list)) #t)
        (else (contain? symbol (cdr list)))))

(define (encode-symbol symbol tree)
  (cond ((leaf? tree) '())
        ((contain? symbol (symbols (left-branch tree)))
          (cons 0 (encode-symbol symbol (left-branch tree))))
        (else
          (cons 1 (encode-symbol symbol (right-branch tree))))))

(encode '(A B A B A C D D D D) sample-tree)
;;;(0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0)

(decode '(0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 0 1 1 0) sample-tree)
;;;(A B A B A C D D D D)

問2.69 Huffman符号化木を生成する

st

問2.70


(define tree (generate-huffman-tree '((a 2) (na 16) (boom 1) (Sha 3) (Get 2) (yip 9) (JOB 2) (Wah 1))))

(encode '(Get a JOB Sha na na na na na na na na Get a JOB Sha na na na na na na na na Wah yip yip yip yip yip yip yip yip yip Sha boom) tree)
;;
;;(0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0)


(decode '(0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0) tree)
;;
;;(Get a JOB Sha na na na na na na na na Get a JOB Sha na na na na na na na na Wah yip yip yip yip yip yip yip yip yip Sha boom)

gist.github.comを使って貼ってみる 00:34

まとまったコードなら良いかも

2.3.3 集合の表現 00:02

集合とはオブジェクトの集まりであり、その実装にはデータ抽象の表現が使える.

和集合、 積集合、 要集合へ加える・合に含まれてか確認するする手続きを実装する.

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))

(if (element-of-set? 9 '(1 2 3)) "it's an element of set" "it's not an element.")
;;; "it's not an element."

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

(adjoin-set 123 '(1 2 3 4 5))
;;; (123 1 2 3 4 5)

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

(define (make-set list)
  (define (iterate result list)
    (if (null? list)
        result
        (iterate (adjoin-set (car list) result) (cdr list))))
  '() list)

(let ((x1 (make-set '(1 2 3 apple 99 beef cat 1024)))
      (x2 (make-set '(2 3 orange 4 10 cat dog apple 99))))
  (intersection-set x1 x2))
;;;(2 3 apple 99 cat)

この実装だと element-of-set がそれぞれの処理で多用されている。

element-of-set は集合のオブジェクトを走査するので、計算量は Θ(n)

になり、積集合の intersection-set は集合のオブジェクトを element-of-set

を使って走査するので Θ(n^2) になる。

問2.59 和集合の実装

と計算量の問題を前振りしておいて、突然問題が出る。

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((element-of-set? (car set1) set2)
         (union-set (cdr set1) set2))
        (else (cons (car set1)
                    (union-set (cdr set1) set2)))))

(let ((x1 (make-set '(1 2 3 apple 99 beef cat 1024)))
      (x2 (make-set '(2 3 orange 4 10 cat dog apple 99))))
  (union-set x1 x2))
;;;(1 2 3 orange 4 10 cat dog apple 99)

問2.60 集合に重複が許される場合

(define (adjoin-set x set)
  (cons x set))

(define (union-set set1 set2)
  (append set1 set2))

順序付けられたリストとしての集合

高速化のために、集合を順序付けられたリストとして表現する、まずは記号はおいといて

整数のみ。集合をソート済みにすることで element-of-set が全要素を走査する必要がなくなり

高速化できることを期待する。

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (car set)) #t)
        ((< x (car set)) #f)
        (else (element-of-set? x (cdr set)))))

(element-of-set? 4 '(1 2 3 4 5 6 7 8))
;;true

(element-of-set? 22 '(1 2 3 4 5 6 7 8))
;;false

この実装で計算量は、最悪の場合 Θ(n) 最善の場合 Θ(1) になる

(集合が均一な場合)平均すると Θ(n/2) になる。まだΘ(n)の増加だけど1/2になった。

積集合の場合、集合同士の最初の要素を比較することで、大幅な計算量の節約ができそう


(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1 (intersection-set (cdr set1) (cdr set2))))
              ((> x1 x2)
               (intersection-set set1 (cdr set2)))
              ((< x1 x2)
               (intersection-set (cdr set1) set2))))))

(let ((x1 (make-set '(1 2 3 99 100 201 202)))
      (x2 (make-set '(2 3 4 10 99 104 202))))
  (intersection-set x1 x2))
;;;(2 3 99 202)

最悪のケースでもそれぞれの集合の要素数の和で済みそうなので、ほぼΘ(n)で

以前の Θ(n^2) に比べるとずいぶん良くなった。

問2.61 集合を順序付けられたリストとしてadjoin-setを実装する


(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cond ((null? set) (list x))
            ((> x (car set))
             (cons (car set) (adjoin-set x (cdr set))))
            (else
             (cons x set)))))

(define set '(1 2 3 5 6))
(adjoin-set 4 set)
;;;(1 2 3 4 5 6)

(adjoin-set 0 set)
;;;(0 1 2 3 5 6)

(adjoin-set 9 set)
;;;(1 2 3 5 6 9)

問2.62 集合を順序付けられたリストとしてunion-setを実装する


(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
         (let ((x1 (car set1)) (x2 (car set2)))
           (cond ((= x1 x2)
                  (cons x1 (union-set (cdr set1) (cdr set2))))
                 ((> x1 x2)
                  (cons x2 (union-set set1 (cdr set2))))
                 (else
                  (cons x1 (union-set (cdr set1) set2))))))))

(let ((x1 (make-set '(1 2 3 99 100 201 202)))
      (x2 (make-set '(2 3 4 10 99 104 202))))
  (union-set x1 x2))
;;;(1 2 3 4 10 99 100 104 201 202)

二分木としての集合

集合を二分木として表現する、xが集合に含められているか確認するには、xとルートの

値を比較して、大きければ右の木、小さければ左の木を再帰的に処理するので、各ステップ毎に

木のサイズはn/2になり、計算量は Θ(log 2 n) になる。

atement

ただ木の左右バランスが取れていないと、最悪Θ(n)と同じ計算量になる。

;;ソート済みのリストを adjoin-set するとバランスが悪くなる

(define (make-set list result)
  (if (null? list) result
      (make-set (cdr list)
                (adjoin-set (car list) result))))

(make-set '(1 2 3 4 5) '())
;;;(1 () (2 () (3 () (4 () (5 () ())))))
;;;バランスが悪い
1
 \
  2
   \
    3
     \
      4
       \
        5

(make-set '(4 2 5 1 3) '())
;;;(4 (2 (1 () ()) (3 () ())) (5 () ()))
;;;バランス良い
    4
   / \
  2   5
 / \
1   3

問2.63 二分木をリストへ変換する


(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))

(tree->list-1
 (make-set '(3 8 4 2 71 38 8 88 9 28) '()))
;;(2 3 4 8 9 28 38 71 88)
;;(append 左の木 (根の値 . 右の木)) を再帰的に解く


(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))

(tree->list-2
 (make-set '(3 8 4 2 71 38 8 88 9 28) '()))
;;(2 3 4 8 9 28 38 71 88)
;;反復的に解く、結果は同じ

問2.64 ソート済みのリストをバランスの良い二分木へ変換する


(define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

(list->tree '(1 3 5 7 9 11))
;;;(5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

集合と情報検索

データベースを実装するとき、それへのアクセスがしっかり抽象されていれば

今回のように、順序無しリスト -> 順序付きリスト -> 二分木 -> B-tree? 

と試行錯誤できる。

開発の初期は手早くシンプルな実装で、開発メンバへインターフェイスを公開して

システムの性質を考慮しながら改善できる、ってのは判りやすい利点だな。

それもこれも実装が抽象化されているから。

2.3.2 例:記号微分 16:06

記号を使って微分演算を実装していく。

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
          (make-product (multiplier exp)
                        (deriv (multiplicand exp) var))
          (make-product (deriv (multiplier exp) var)
                        (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum a1 a2) (list '+ a1 a2))

(define (make-product m1 m2) (list '* m1 m2))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (addend s) (cadr s))

(define (augend s) (caddr s))

(define (multiplier p) (cadr p))

(define (multiplicand p) (caddr p))

(deriv '(+ 3 x) 'x)
> (+ 0 1)

(deriv '(* y x) 'x)
> (+ (* y 1) (* 0 x))

2.3.1 クォート - 記号データ 16:06

今までの数値だけでなく、記号を扱う。

scheme変数を評価させないとき '(シングルクォート)を使うけど、その理由が面白かった


「あなたの朝食を大声言ってください」  と人に言うと「パン」という答えなんかが返ってくる

「'あなたの朝食'を大声で言ってください」と人に言うと「あなたの朝食」という答えが返ってくるだろう


なるほどなー、'あなたの朝食' を処理系(相手)に評価させないようにするときに使うシングルクォートがその実装の語源、というか元なのか、全然気付かなかったけど、納得。

問2.53 クォートの練習

(define (memq item x)
  (cond ((null? x) false)
        ((eq? item (car x)) x)
        (else (memq item (cdr x)))))

(list 'a 'b 'c)
> (a b c)

(list (list 'george))
> ((george))

(cdr '((x1 x2) (y1 y2)))
> ((y1 y2))

(cadr '((x1 x2) (y1 y2)))
> (y1 y2)

(pair? (car '(a short list)))
> #f

(memq 'red '((red shoes) (blue socks)))
> #f

(memq 'red '(red shoes blue socks))
> #f

トラックバック - http://sicp.g.hatena.ne.jp/tkmr2000/20081124
|