376 Views
January 26, 22
スライド概要
Scheme プログラミング
URL: https://www.kkaneko.jp/pro/scheme/index.html
金子邦彦研究室
URL: https://www.kkaneko.jp/index.html
金子邦彦(かねこくにひこ) 福山大学・工学部・教授 ホームページ: https://www.kkaneko.jp/index.html 金子邦彦 YouTube チャンネル: https://youtube.com/user/kunihikokaneko
sp-16. cons と種々のデータ構 造 (Scheme プログラミング) URL: https://www.kkaneko.jp/pro/scheme/index.html 金子邦彦 1
アウトライン 16-1 ペア 16-2 パソコン演習 16-3 課題 2
16-1 ペア 3
ペアとは 単純なペアの例 ペアとは: apple 100 car cdr 2つの構成部分のペアのこと. car と cdr に分かれる 4
car と cdr • cons は2つの引数を取り,2つの引数を部分と して含むような「ペア」を返す 例) (define x (cons 'apple 100)) • ペアを構成する部分は,car, cdr で取り出せる 例) (car x) (cdr x) → 「apple」が得られる → 「100」が得られる • ペアは,「対」ともいう 5
(cons 'apple 100) の箱とポインタ記法 100 apple ペアとは: 2つの構成部分のペアのこと. car と cdr に分かれる 6
(cons 'apple 100) の箱とポインタ記法 100 car cdr apple 7
(cons 'apple empty) の箱とポインタ記法 apple ペアは,上のように,箱とポインタ表記される 8
(cons 'apple empty) の箱とポインタ記法 car cdr apple 9
まとめ • 「リスト」は末尾が「空リスト」であるような 「ペアの並び」である • ペアの組み合わせによって,複雑な構造を表現で きる 10
16-2 パソコン演習 11
パソコン演習の進め方 • 資料を見ながら,「例題」を行ってみる • 各自,「課題」に挑戦する • 自分のペースで先に進んで構いません 12
DrScheme の使用 • DrScheme の起動 • 今日の演習では「Full Scheme」 に設定 プログラム → PLT Scheme → DrScheme Language → Choose Language → Full Scheme → OK → 「Execute ボタン」 13
Full Scheme では • ペアが,自由に扱えるようになる • 但し,「empty」が使えなくなる ので,代わりに「'()」を使う • Full Scheme で empty を使おうとす るとエラー • リストの表示が変わる (list 15 8 6) ⇒ (15 8 6) のように 14
例題1.ペア • シンボルと数値のペアを作る • ペアを生成するために cons を使う • ペアを構成する部分('apple や 100 など)を 取り出すために car, cdr を使う 変数x: シンボル 'apple と数値 100 のペア 変数y: シンボル 'orange と数値 60 のペア 変数z: シンボル 'banana と数値 80 のペア 15
「例題1.ペア」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define x (cons 'apple 100)) (define y (cons 'orange 60)) (define z (cons 'banana 80)) 2. その後,次を「実行用ウインドウ」で実行しなさい x (car x) (cdr x) ☆ 次は,例題2に進んでください 16
ペアの生成 表示されたペア 17
例題2.リストの変数定義 • リスト 15, 8, 6 を変数として定義し, 名前Aを付ける • 変数を定義するために define を使う • リストを作るために cons を使う 18
「例題2.リストの変数定義」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define A (cons 15 (cons 8 (cons 6 '())))) 2. その後,次を「実行用ウインドウ」で実行しなさい A (car A) (cdr A) ☆ 次は,例題3に進んでください 19
「'()」は,空リストの意味 20
(cons 15 (cons 8 (cons 6 '()))) の箱とポインタ記法 15 8 6 • リストの要素が,「ペアの並び」と して順順につながる 21
(cons 15 (cons 8 (cons 6 '()))) の箱とポインタ記法 car 15 6 8 cdr 22
リストの car と cdr car • リストの car: 15 • リストの先頭要素 6 8 cdr • リストの cdr: • リストから先頭要素を取り除いた残り(やはりリスト) 23
リストの末尾としての空リスト 15 8 6 「空リストである」こと を示す特別な値が 入っている 24
リストを構成するペアの性質 (1/2) 15 8 6 • リストを構成するペアの個数:リストの要素数に 等しい • リストを構成するペアの car: リストの要素が入 る 25
リストを構成するペアの性質 (2/2) 15 8 6 • リストを構成するペアの右側のセル(cdr フィールド) • 次の要素へのポインタか,「空リスト」であることを示す 特別な値(リストの末端であることを示す)が入る 26
リストとは • Scheme では 末尾が「空リスト」であるようなペアの並び • 並びの最後のペアの cdr フィールドに空リスト が入っ ている • 行儀の良いリスト(proper list)と呼ぶこともある 27
(cons 6 '()) car 6 cdr (cdr は空リスト) (cons 8 (cons 6 '())) car 8 6 cdr (cons 15 (cons 8 (cons 6 '()))) car 15 6 8 cdr 28
cons の意味 • リストでは: • リストと要素をつなげて,新しいリスト を作る • 一般的には: • データとデータをつなげて,新しいペア を作る 29
例題3.ペアから構成されたペア • 下記のペアを,変数aとして定義する 3 4 car 1 2 cdr 30
「例題3.ペアから構成されたペア」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define a (cons (cons 1 2) (cons 3 4))) 2. その後,次を「実行用ウインドウ」で実行しなさい a (car a) (cdr a) ☆ 次は,例題4に進んでください 31
ペアの生成 表示されたペア 32
例題3のプログラム例 (define a (cons (cons 1 2) (cons 3 4))) ペアから構成されたペアは, 「cons の入れ子」で書ける 33
(cons (cons 'a 'b) 'c) の箱とポインタ記 法 'c cdr car 'a 'b 34
(cons 'a (cons 'b 'c)) の箱とポインタ記 法 car 'a 'b 'c cdr 35
cons によるペアの表記 36
例題4.car と cdr の組み合わせ • 例題3のペアについて,car と cdr を組 み合わせて,「1」,「2」,「3」, 「4」を得る 3 1 4 2 37
「例題3.car と cdr の組み合わせ」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define a (cons (cons 1 2) (cons 3 4))) 2. その後,次を「実行用ウインドウ」で実行しなさい (car (car a)) (cdr (car a)) (car (cdr a)) (cdr (cdr a)) (caar a) (cdar a) (cadr a) (cddr a) ☆ 次は,例題4に進んでください 38
39
40
例題4のプログラム例 (define a (cons (cons 1 2) (cons 3 4))) (car (car a)) (cdr (car a)) (car (cdr a)) (cdr (cdr a)) 41
car, cdr の組み合わせ 3 1 4 (car (cdr a)) (cdr (cdr a)) 2 (car (car a)) (cdr (car a)) 42
car, cdr の組み合わせ • (caar pair) • (cadr pair) ... • (cdddr pair) car, cdr を4つまで組み合わせることができる 43
ペアに関する関数 • (cons obj1 obj2) ペアの生成 • (car pair) car の取り出し • (cdr pair) cdr の取り出し • (caar pair) • (cadr pair) ... • (cdddr pair) car, cdr を4つまで組み合わせることができる 44
例題5. cons と list の組み合わせ(1) • 下記のようなペアの集まりを,変数 xとして定義する cdr 5 4 6 car 1 2 3 45
cons と list の組み合わせ (1/2) cdr 5 4 6 car 1 2 3 (define x (cons (list 1 2 3) (list 4 5 6))) 46
47
48
例題6. cons と list の組み合わせ(2) • 下記のようなペアの集まりを,変数 xとして定義する b a car 20 cdr 10 y x 49
cons と list の組み合わせ (2/2) b a car 20 cdr 10 y x (define x (list (cons 'x 'y) (cons 'a 'b) (cons 10 20))) 50
51
例題7. list と list の組み合わせ • 下記のようなペアの集まりを,変数 xとして定義する cdr 3 car 1 4 2 52
list と list の組み合わせ cdr 3 car 1 4 2 (define x (list (list 1 2) (list 3 4))) 53
54
ドット対の例 (cons 'a 'b) ⇒ (a . b) と表示される (cons (cons 'a 'b) 'c) ⇒ ((a . b) . c) と表示される (cons 'a (cons 'b 'c)) ⇒ (a b . c) と表示される (cons (cons 'a 'b) (cons 'c 'd)) ⇒ (( a . b) c . d) と表示される 55
56
ドット対 • ペアの cdr がリストになっていない場合 • つまり,cdr 方向にペアの並びをみたときに,末 尾が「空リスト」になっていなければ ⇒ ドットを,末尾の要素の前に追加 57
2 (cons 1 2) (1 . 2) 1 3 (cons (cons 1 2) 3) ((1 . 2) . 3) 2 1 (1 2 . 3) (cons 1 (cons 2 3)) 1 2 3 58
16-3 課題 59
課題① • 実行結果を報告しなさい • 実行上の注意: DrScheme で,必ず「Full Scheme」を選んでから実行すること. (list (cons 1 2) (cons 3 4)) (list (list 1 2) (list 3 4)) (car (list ...)) の実行 結果 (cdr (list ...)) の実行 結果 (cadr (list ...)) の実 行結果 (cddr (list ...)) の実 行結果 60
さらに勉強したい人への 補足説明事項 二分探索木 61
例題8.二分探索木 例題9.二分探索木による探索 ・入れ子になった構造 62
木構造 • 幾つかの節点(node)と,それらを結ぶ枝(branch)か ら構成 • 節点がデータに対応 • 枝がデータ間の親子関係に対応 • 子: 節点の中で下方に分岐する枝の先にあるもの • 親: 分岐元の節点 親 節点(node) 枝(branch) 子 図.単純な木構造 63
木構造 根(root) 葉(leaf) 部分木 • 根(root): 木の一番上の節点を根(root) • 葉(leaf): 子を持たない節点 • 部分木: 木の中のある節点を相対的な根と考えた ときの,そこから枝分かれした枝と節点の集合 64
二分木 (binary tree) • 木構造で,各節点から出る枝が二本以下のも の • 木構造に関するアルゴリズムの中で,中心的 なデータ構造 65
二分探索木 (binary search tree) • 二分木の一種 • データの配置に規則あり • 左側のすべての子は親より小さい • 右側のすべての子は親より大きい • データの探索のためのデータ構造 35 21 13 46 40 61 69 66
二分探索木による探索 • 根(root)から始める • 探索キーの値と,各節点のデータを比較し, 目標となるデータを探す • 探索キーよりも節点のデータが小さいときは,右 側の子をたどる • 探索キーよりも節点のデータが大きいときは,左 側の子をたどる 67
二分探索木による探索の例 (例) 40である節点を探す場合 1. 根の値(35)と,探索キー(40)を比較 2. 探索キーの方が大きいので,右側の子節点へ移る 3. 次に移った節点の値(46)と探索キー(40)を比較し 4. 探索キーの方が小さいので,左の子節点へ移る 5. 次に移った節点(40)が,目標の節点である 35 21 13 46 40 61 69 68
データ構造 • 複雑なプログラムを作成する時,データ構造 について考える必要がある • データ構造 • アルゴリズムを容易にするために工夫されたデー タの並び • 基本的なデータ構造は,配列,キュー,スタック, リスト構造,木構造など 69
二分探索木のための node structure (define-struct node value (value left right)) left right 枝 枝 value left value right left right 70
例題8.二分探索木 • 二分探索木のプログラムを作り,実行する • 二分探索木の節点を扱うために,define struct 文を 使って,node structure を定義する • 1つの二分探索木は,節点が集まって,入れ子の構造 になる 71
二分探索木の節点 • 二分探索木の節点を,define-struct 文を使って定義する 名前 (define-struct node (value left right)) 属性の並び (それぞれの属性にも名前がある) 72
define-struct の機能 (define-struct node (value left right)) • 上記のプログラムの実行によって • make-node • node-value 属性 value, left, • node-left right の取得 • node-right が使えるようになる 73
(make-node 35 (make-node 21 (make-node 13 false false) false) (make-node 46 (make-node 40 false false) (make-node 61 false (make-node 69 false false)))) 35 21 13 上のプログラムが表現する 2分探索木 (「false」は「データが無い」こと を示す特別な値) 46 40 61 69 74
例題9.二分探索木による探索 • 二分探索木の探索のプログラムを作り, 実行する • データが二分探索木の中にあれば → true • 無ければ → false 75
(define-struct node (value left right)) (define (search x a-tree) (cond 左を探す [(eq? a-tree false) false] [(< x (node-value a-tree)) (search x (node-left a-tree))] [(< (node-value a-tree) x) (search x (node-right a-tree))] [else true])) 右を探す 76
77
まとめ • 2分探索木を「入れ子になった node structure」 として表現した 78