Schemeにおけるペア（cons ）の仕組みと、ペアを
用いたリストや木構造などのデータ構造の表現
【学習内容の構成】
1. ペアの基本：consによる2つの要素の結合、car
とcdrによる要素の取り出し
2. リストの構造：末尾が空リストであるペアの並
びとしてのリスト表現
3. 複合データ構造：consとlistの組み合わせによる
入れ子構造、二分探索木への応用
• 前提：Schemeの基本文法、リストの概念
• 意義：複雑なデータ構造をペアの組み合わせで表
現する原理の理解
2
16-1 ペア
3
apple
100
car
cdr
ペアとは： ２つの構成部分のペアのこと．
car と cdr に分かれる
単純なペアの例
ペアとは
4
• cons は２つの引数を取り，２つの引数を部分と
して含むような「ペア」を返す
例） (define x (cons 'apple 100))
• ペアを構成する部分は，car, cdr で取り出せる
例） (car x) → 「apple」が得られる
(cdr x) → 「100」が得られる
• ペアは，「対」ともいう
car と cdr
5
１００
apple
ペアとは： ２つの構成部分のペアのこと．
car と cdr に分かれる
(cons 'apple 100) の箱とポインタ記法
6
１００
apple
car
cdr
(cons 'apple 100) の箱とポインタ記法
7
apple
ペアは，上のように，箱とポインタ表記される
(cons 'apple empty) の箱とポインタ記法
8
apple
car
cdr
(cons 'apple empty) の箱とポインタ記法
9
• 「リスト」は末尾が「空リスト」であるような
「ペアの並び」である
• ペアの組み合わせによって，複雑な構造を表現で
きる
まとめ
10
16-2 パソコン演習
11
• 資料を見ながら，「例題」を行ってみる
• 各自，「課題」に挑戦する
• 自分のペースで先に進んで構いません
パソコン演習の進め方
12
• DrScheme の起動
プログラム → PLT Scheme → DrScheme
• 今日の演習では「Full Scheme」
に設定
Language
→ Choose Language
→ Full Scheme
→ OK
→ 「Execute ボタン」
DrScheme の使用
13
• ペアが，自由に扱えるようになる
• 但し，「empty」が使えなくなる
ので，代わりに「'()」を使う
• Full Scheme で empty を使おうとす
るとエラー
• リストの表示が変わる
(list 15 8 6) ⇒ (15 8 6) のように
Full Scheme では
14
• シンボルと数値のペアを作る
• ペアを生成するために cons を使う
• ペアを構成する部分（'apple や 100 など)を
取り出すために car, cdr を使う
変数x： シンボル 'apple と数値 100 のペア
変数y: シンボル 'orange と数値 60 のペア
変数z: シンボル 'banana と数値 80 のペア
例題１．ペア
15
1. 次を「定義用ウインドウ」で，実行しなさい
• 入力した後に，Execute ボタンを押す
(define x (cons 'apple 100))
(define y (cons 'orange 60))
(define z (cons 'banana 80))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆ 次は，例題２に進んでください
x
(car x)
(cdr x)
「例題１．ペア」の手順
16
ペアの生成
表示されたペア
17
• リスト 15, 8, 6 を変数として定義し，
名前Aを付ける
• 変数を定義するために define を使う
• リストを作るために cons を使う
例題２．リストの変数定義
18
1. 次を「定義用ウインドウ」で，実行しなさい
• 入力した後に，Execute ボタンを押す
(define A (cons 15 (cons 8 (cons 6 '()))))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆ 次は，例題３に進んでください
A
(car A)
(cdr A)
「例題２．リストの変数定義」の手順
19
「'()」は，空リストの意味
20
１５
８
６
• リストの要素が，「ペアの並び」と
して順順につながる
(cons 15 (cons 8 (cons 6 '()))) の箱とポインタ記法
21
１５
８
６
car
cdr
(cons 15 (cons 8 (cons 6 '()))) の箱とポインタ記法
22
１５
８
６
car
cdr
• リストの car:
• リストの先頭要素
• リストの cdr:
• リストから先頭要素を取り除いた残り（やはりリスト）
リストの car と cdr
23
１５
８
６
「空リストである」こと
を示す特別な値が
入っている
リストの末尾としての空リスト
24
１５
８
６
• リストを構成するペアの個数：リストの要素数に
等しい
• リストを構成するペアの car： リストの要素が入
る
リストを構成するペアの性質 (1/2)
25
１５
８
６
• リストを構成するペアの右側のセル(cdr フィールド)
• 次の要素へのポインタか，「空リスト」であることを示す
特別な値（リストの末端であることを示す）が入る
リストを構成するペアの性質 (2/2)
26
• Scheme では
末尾が「空リスト」であるようなペアの並び
• 並びの最後のペアの cdr フィールドに空リスト が入っ
ている
• 行儀の良いリスト（proper list）と呼ぶこともある
リストとは
27
１５
８
６
car
cdr
(cons 15 (cons 8 (cons 6 '())))
８
６
car
cdr
(cons 8 (cons 6 '()))
６
car
cdr （cdr は空リスト）
(cons 6 '())
28
• リストでは：
• リストと要素をつなげて，新しいリスト
を作る
• 一般的には：
• データとデータをつなげて，新しいペア
を作る
cons の意味
29
• 下記のペアを，変数aとして定義する
１
２
３
４
cdr
car
例題３．ペアから構成されたペア
30
1. 次を「定義用ウインドウ」で，実行しなさい
• 入力した後に，Execute ボタンを押す
(define a (cons (cons 1 2)
(cons 3 4)))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆ 次は，例題４に進んでください
a
(car a)
(cdr a)
「例題３．ペアから構成されたペア」の手順
31
ペアの生成
表示されたペア
32
(define a (cons (cons 1 2)
(cons 3 4)))
ペアから構成されたペアは，
「cons の入れ子」で書ける
例題３のプログラム例
33
'c
car
cdr
'a
'b
(cons (cons 'a 'b) 'c) の箱とポインタ記
法
34
car
cdr
'a
'b
'c
(cons 'a (cons 'b 'c)) の箱とポインタ記
法
35
cons によるペアの表記
36
• 例題３のペアについて，car と cdr を組
み合わせて，「１」，「２」，「３」，
「４」を得る
１
２
３
４
例題４．car と cdr の組み合わせ
37
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)
「例題３．car と cdr の組み合わせ」の手順
38
39
40
(define a (cons (cons 1 2)
(cons 3 4)))
(car (car a))
(cdr (car a))
(car (cdr a))
(cdr (cdr a))
例題４のプログラム例
41
１
２
３
４
(car (car a))
(cdr (car a))
(car (cdr a))
(cdr (cdr a))
car, cdr の組み合わせ
42
• (caar pair)
• (cadr pair)
...
• (cdddr pair)
car, cdr を４つまで組み合わせることができる
car, cdr の組み合わせ
43
• (cons obj1 obj2)
ペアの生成
• (car pair)
car の取り出し
• (cdr pair)
cdr の取り出し
• (caar pair)
• (cadr pair)
...
• (cdddr pair)
car, cdr を４つまで組み合わせることができる
ペアに関する関数
44
• 下記のようなペアの集まりを，変数
xとして定義する
car
1
2
3
4
5
6
cdr
例題５． cons と list の組み合わせ(1)
45
car
(define x (cons (list 1 2 3)
(list 4 5 6)))
1
2
3
4
5
6
cdr
cons と list の組み合わせ (1/2)
46
47
48
• 下記のようなペアの集まりを，変数
xとして定義する
car
x
y
b
cdr
a
20
10
例題６． cons と list の組み合わせ(2)
49
car
(define x (list (cons 'x 'y)
(cons 'a 'b)
(cons 10 20)))
x
y
b
cdr
a
20
10
cons と list の組み合わせ (2/2)
50
51
• 下記のようなペアの集まりを，変数
xとして定義する
car
1
2
cdr
3
4
例題７． list と list の組み合わせ
52
car
(define x (list (list 1 2)
(list 3 4)))
1
2
cdr
3
4
list と list の組み合わせ
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
１
２
(cons 1 2)
(1 . 2)
１
２
(cons (cons 1 2) 3)
((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
例題８．二分探索木
例題９．二分探索木による探索
・入れ子になった構造
62
• 幾つかの節点(node)と，それらを結ぶ枝(branch)か
ら構成
• 節点がデータに対応
• 枝がデータ間の親子関係に対応
• 子： 節点の中で下方に分岐する枝の先にあるもの
• 親： 分岐元の節点
親
子
枝(branch)
節点(node)
図．単純な木構造
木構造
63
• 根(root)： 木の一番上の節点を根(root)
• 葉(leaf)： 子を持たない節点
• 部分木： 木の中のある節点を相対的な根と考えた
ときの，そこから枝分かれした枝と節点の集合
部分木
根(root)
葉(leaf)
木構造
64
• 木構造で，各節点から出る枝が二本以下のも
の
• 木構造に関するアルゴリズムの中で，中心的
なデータ構造
二分木 (binary tree)
65
• 二分木の一種
• データの配置に規則あり
• 左側のすべての子は親より小さい
• 右側のすべての子は親より大きい
• データの探索のためのデータ構造
35
21
13 40 61
46
69
二分探索木 (binary search tree)
66
• 根(root)から始める
• 探索キーの値と，各節点のデータを比較し，
目標となるデータを探す
• 探索キーよりも節点のデータが小さいときは，右
側の子をたどる
• 探索キーよりも節点のデータが大きいときは，左
側の子をたどる
二分探索木による探索
67
(例） 40である節点を探す場合
1. 根の値(35)と，探索キー(40)を比較
2. 探索キーの方が大きいので，右側の子節点へ移る
3. 次に移った節点の値(46)と探索キー(40)を比較し
4. 探索キーの方が小さいので，左の子節点へ移る
5. 次に移った節点(40)が，目標の節点である
35
21
13 40 61
46
69
二分探索木による探索の例
68
• 複雑なプログラムを作成する時，データ構造
について考える必要がある
• データ構造
• アルゴリズムを容易にするために工夫されたデー
タの並び
• 基本的なデータ構造は，配列，キュー，スタック，
リスト構造，木構造など
データ構造
69
(define-struct node
(value left right))
left right
value
left right
value
left right
value
枝
枝
二分探索木のための node structure
70
• 二分探索木のプログラムを作り，実行する
• 二分探索木の節点を扱うために，define struct 文を
使って，node structure を定義する
• １つの二分探索木は，節点が集まって，入れ子の構造
になる
例題８．二分探索木
71
• 二分探索木の節点を，define-struct
文を使って定義する
(define-struct node
(value left right))
名前
属性の並び
（それぞれの属性にも名前がある）
二分探索木の節点
72
define-struct の機能
• 上記のプログラムの実行によって
• make-node
• node-value
• node-left
• node-right
が使えるようになる
(define-struct node
(value left right))
属性 value, left,
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 40 61
46
69
上のプログラムが表現する
２分探索木
（「false」は「データが無い」こと
を示す特別な値）
74
• 二分探索木の探索のプログラムを作り，
実行する
• データが二分探索木の中にあれば
→ 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
• ２分探索木を「入れ子になった node structure」
として表現した
まとめ
78
