Document

5. 任意長の合成データ：リスト
プログラミング論I
本日の内容
1.リスト：有限だが不定数の要素を持つ
(参考：構造体は要素数が確定している)
– 事前に要素数を確定できないデータを処理する場合
2. Scheme プログラムでのリストの記法
リスト関連：cons list first rest empty? list?
3.任意数の要素を含むリストの再帰的データ定義
4.リストを処理する再帰的な関数の設計法
リストとは
• 不定数のデータの並び(合成データ)
• データの並びには順序があり操作は先頭側から
要
素
を
加
え
だ
ん
だ
ん
長
く
23, 32, 6, 8 の順にリストに加える例
終端
最初は空
23
23を加える
32を加える
32
23
6
32
23
6
32
23
同様に続く…
先頭側：後から
加えた側。操作
はこちらから
8
終端側：
先に加え
た要素は
こちら側
リストの作成：cons
空リスト emptyから始め cons を用いてリストを作成
(cons 追加する先頭要素追加されるリスト)
empty
(cons 23 empty)
(cons 32
(cons 23 empty))
最初は空
23を加える
23
32を加える
32
23
6
32
23
6
32
23
…
同様に…
(cons 8
(cons 6
8
(cons 32
(cons 23 empty))))
Scheme でのリストの記法
consを使うリストの表記 (長くて見にくい?)
8
6
32
23
終端
(cons 8 (cons 6 (cons 32 (cons 23 empty)))
listを使った省略記法(以降の説明ではこの記法)
(list 8 6 32 23)
要素データの並び
これ自体が1つのデータ値(式)
合成データなので複数の要素データを含み得る
C言語でのリストのプログラム
data *next
8
6
NULL
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int data;
struct _node *next;
}node_t;
void printList(node_t *p){
while (p != NULL){
printf("data=%d\n", p->data);
p = p->next;
}
}
int main(){
node_t a, b, c, d;
a.data=8; a.next=&b;
b.data=6; b.next=&c;
c.data=32; c.next=&d;
d.data=23; d.next=NULL;
printList(&a);
return(0);
}
Schemeでは，上記を以下のように書ける
(list 8 6 32 23)
C言語でのリストのプログラム
data *next
8
6
NULL
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 1
#define FAILURE 0
typedef struct _node{
int data;
struct _node *next;
}node_t;
// newNode:int, node_t* -> node_t*
node_t *newNode(int d, node_t* p){
node_t *np=(node_t *) malloc(sizeof (node_t));
if (np == NULL){
fprintf(stderr, “Memory allocation error.”);
return NULL;
}
np->data = d;
np->next = p;
return np;
}
int prepend(int d, node_t **pp){
node_t = *p;
p = newNode(d, *pp);
if (p == NULL) return FAILURE;
*pp = p;
return SUCCESS;
}
void printList(node *p){
while (p != NULL){
printf(“%d “, p->data);
p = p->next;
}
}
void main(){
node_t *p=NULL;
prepend(23, &p);
prepend(32, &p);
prepend(6, &p);
prepend(8, &p);
Schemeでは，
printList(p);
上記を以下の
}
ように書ける
(list 8 6 32 23)
C言語でのリストのプログラム
data *next
8
6
NULL
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 1
#define FAILURE 0
typedef struct _node{
int data;
struct _node *next;
}node_t;
// newNode:int, node_t* -> node_t*
node_t *newNode(int d, node_t* p){
node_t *np=(node_t *) malloc(sizeof (node_t));
if (np == NULL){
fprintf(stderr, “Memory allocation error.”);
return NULL;
}
np->data = d;
np->next = p;
return np;
}
int append(int d, node_t **pp){
node_t = *p;
p = newNode(d, NULL);
if (p == NULL) return FAILURE;
while(*pp != NULL)
pp = &((*pp)->next);
*pp = p;
return SUCCESS;
}
void printList(node *p){
while (p != NULL){
printf(“%d “, p->data);
p = p->next;
}
}
void main(){
node_t *p=NULL;
append(23, &p);
append(32, &p);
append(6, &p);
Schemeでは，
append(8, &p);
上記を以下の
printList(p);
ように書ける
}
(list 23 32 6 8)
リスト要素の参照：first と rest
(構造体は定義に応じたフィールドのセレクタで要素参照)
リストの場合 → どのリストでもセレクタは first とrest
first
15
rest
8
6
32
23
終端
• first：先頭の要素を参照するセレクタ
(first (list 15 8 6 32 23)) は 15
• rest：先頭を除いた残りのリストを参照するセレクタ
(rest (list 15 8 6 32 23)) は(list 8 6 32 23)
例）上のリストの rest の rest の rest の first は：32
例題1.リストの first と rest の例
先のリストの rest の rest の rest の first は?
計算は最内括弧から行う点に注意
(first (rest (rest (rest (list 15 8 6 32 23)))))
first部 rest部
= (first (rest (rest (list 8 6 32 23))))
first部 rest部
= (first (rest (list
6 32 23)))
first部 rest部
= (first (list 32 23))
first部 rest部
= 32
実行結果
特別なリストemptyとリスト処理のエラー
empty は「空リスト」を表す特別な定数記号
(数でいう 0 のようなもの)
「(空でない)非空のリスト」だけ firstやrest が実行でき
る。 empty はリストだが要素参照はできない。
演算
非空リスト空リスト
empty
リスト以外
(数など)
first OK
実行エラー
実行エラー
rest
実行エラー
実行エラー
OK
データの属性判定：list? empty?
演算と対象データの組合わせによってはエラーに!
→ 適切な属性判定により正しく処理を進行
• list? ：リストであるか調べる
– 「リスト」ならば true （さもなければ false）
• empty? ：空リストであるかを調べる
– 「空リスト」ならば true （さもなければ false）
リストに関するここまでのまとめ
•空リスト emptyから始め cons でより長いリストを
組み立てる
(cons x a_list) :a_listの先頭にx を加えたリスト
•要素の列挙でも記述できる：(list 要素の並び)
（例） (list 15 8 6 32 23)
•リストに関する他の演算子
(first a_list) はリスト a_list の先頭の要素
(rest a_list) はリスト a_list の先頭を除いた残り
(list? a_list) はリスト a_list がリストかどうか判断
(empty? a_list) はリスト a_list が空リストか判断
練習1
1. 先頭から1, 2, 3 の順に数が並ぶリスト Lを書け
2. 前述1のリスト Lの先頭に0を加える式を書け
3. 前述1のリスト Lのrest の rest の first を
求めよ。それは何番目の要素か?
4. 次の組合せの結果を書け(「エラー」ならエラーと記入)
L=(list 1) の場合 L=(list 1 2)
(first L) の結果
(rest L)
(first (rest L))
L=(list 1 2 3)
リストの再帰的データ定義と
再帰的なリスト処理関数の設計法
任意長であるリストの再帰的データ定義
リスト：不定要素数を含む合成データ
要素数を固定しない場合の定義は? →再帰
整数リストの例：すべての整数リストは以下のどちらか
* 最初の空リスト (空リストから開始して，より長いリストを構築)
* 整数と，他の整数リストを用いて作られた整数リスト
整数リスト loi (list-of-integers) は以下のいずれか
1. 空リスト empty, もしくは
2. (cons i loi) ここで i は整数、loi は整数リスト
定義はそれ自身を参照(整数リストが何かを整数リストで説明)．
Self-Referential(自己参照) または Recursive(再帰的) と呼ぶ．
上記で2は自己参照を持つが，1は持たない(自己参照の停止)．
プログラム設計法：再帰データの関数
再帰データを扱う関数向けにプログラム設計法を拡張
•データの解析と定義:
•対象は任意数の要素を持つ → 再帰的(自己参照)データ定義が必要 (少な
くとも2つの節を含み、少なくとも1つの節は自己参照してはならない)
• Purpose:プログラムの目的を理解、機能の概要を記述
•Contract, Header, Statement:
• Example:プログラムの振る舞いを「例」で記述．
• Template:
•データ定義と同数の節を持つcond式で定式化
•セレクタ式(rest)に対する自己適用(自然再帰Natural Recursion)
• Body Definition:
•まず基底ケース (再帰を含まないcond節)から開始
•次に自己参照のケース。再帰的適用に対し関数は目的記述文の通りに機
能すると想定→ あとは結果への値の結合についての問題。
• Test:検査を通じた誤り（エラー）の発見
リスト処理の再帰関数のテンプレート
リスト処理関数のテンプレート
節2つと自己参照1つを持つcond式が本体式
(define (fun-for-list a_list)
セレクタrestの結
(cond
果値へ自己適用
要素がなければ繰り返さない
(先頭をとった残りの
データ定 [(empty? a_list) …]
リストを繰返し処理)
義と同様 [else … (first a_list) …
2つの節
… (fun-for-list (rest a_list)) …]))
リスト処理の再帰関数の本体定義
まず基底ケース(再帰を含まないcond節)から開始
通常、対応する答えは定式化が容易か、あるいは例により既知。
次に自己参照のケースを扱う。
再帰的な適用 (関数は目的記述文通りに機能すると想定)
→ あとは必要に応じて値を結合することを検討。
結果値の生成(部分的な結果を結合し最終結果へ):
– 多くの場合、結合は基本処理(+ and consなど)で実現
– もし first項のデータに対して何らかのチェックが必要なら
入れ子のcondが必要なことが考えられる．
– 場合により補助関数を導入することも必要．
例題2. リストの長さ(要素数)
整数リストの要素数を求める関数 how-many
入力
how-many
整数のリスト
例：(list 11 12)
入力はリスト：任意長の再帰データ
出力
数
例：2
リスト処理の再帰関数のテンプレート
リスト処理関数のテンプレート
2つの節と1つの矢印を持つcond式を持つ(テキスト表現
では矢印の代わりにセレクタ式への関数の自己適用)
整数のリストを処理する関数のテンプレート例
(define (fun-for-loi a_loi)
セレクタrestの結
果値へ自己適用
(cond 要素がなければ繰り返さない
(先頭をとった残りの
データ定 [(empty? a_loi) …]
リストを繰返し処理)
義と同様 [else … (first a_loi) …
2つの節
… (fun-for-loi (rest a_loi)) …]))
リスト処理の再帰関数の本体定義
例：関数 how-many (整数リストの要素数を計算する)
;; how-many : list-of-integers -> number
;; to determine how many integers are on a_loi
(define (how-many a_loi)
(cond [(empty? a_loi) …]
[else … (first a_loi) …
… (how-many (rest a_loi)) …]))
テンプレート
• 基底ケースの答は0 (空リストの要素数は0)
• 第2節はfirst項の要素数とrest項の要素数を計算して結合
→ a_loiの要素数は後者の式の値に1を加えるだけ：
(define (how-many a_loi)
(cond [(empty? a_loi) 0]
[else (+ 1 (how-many
(rest a_loi)))]))
例題2. リストの長さ(要素数)
1. リストが空ならば： → 基底(再帰的繰返しの終了)
解は 0
→ 自明な解(要素がないので個数0)
2. そうでなければ、first部の部分解、 rest部への再帰処理に
よる部分解、これら部分解から最終解の生成を考える：
• リストの rest （これもリスト）の長さに1を足したものが解
．．．
．．．
first部は
要素数1
rest 部の要素数を求める(再帰的繰返し)
足すと全体の要素数になる
例題2. リストの長さ(要素数)
No
(empty? a_list)
Yes
(+ 1
(how-many (rest a_list)))
再帰で繰り返し
0 が自明な解である
例題2. リストの長さ(要素数) how-many 関数
値を1つ受け取る（入力）
関数定義を示
a_list の値からリストの
すキーワード関数の名前
長さを求める（出力）
(define (how-many a_list)
(cond
再帰の停止条件
[(empty? a_list) 0] 基底ケースと解
[else (+ 1
(how-many (rest a_list)))]))
• how-many 内に how-many がある：再帰で繰返す
例： (how-many
(list 11 12))
→ (+ 1 (how-many (list 12)))
まさに「再帰」である
C言語でのhowmany
int howmany(node_t *a_list){
if (a_list == NULL) return 0;
else return 1+howmany(a_list->next);
}
int howmany(node_t *a_list){
int sum=0;
while (a_list != NULL){
sum ++;
a_list = a_list->next;
}
return sum;
}
(how-many (list 11 12)) から
2 が得られる過程の概略
(how-many (list 11 12))
(list 11 12)の長さ
= ...
=(+ 1 (how-many (list 12)))
= ...
(list 12)の長さに1を足す
=(+ 1 (+ 1 (how-many empty)))
= ...
=(+ 1 (+ 1 0))
=(+ 1 1)
=2
empty の長さに1＋1を足す
練習2. 数値リストの要素の和
数値リストの要素を合計する関数list-sumを作れ
list-sum
入力
数のリスト
例：(list 1 2 3)
入力はリスト：任意長の再帰データ
出力
数
例：6
–
テンプレートを使う(how-manyとほぼ同じ)
–
主な違い：cond式の第2節ではfirst項の要素値
とrest項(リスト)に対する部分結果値を合計
例題3. リストが「5」を含むか調べる
•
リストの要素の中に「5」を含むかどうか調
べる関数 contains-5? を作る。
入力は
1つのリスト
contains-5?
(list 3 5 7 9)
•
出力はブール値
(trueかfalse)
true
リスト処理再帰関数のテンプレートを使う
リスト処理の再帰関数の本体定義
まず基底ケース(再帰を含まないcond節)から開始
通常、対応する答えは定式化が容易か、あるいは例により既知。
次に自己参照のケースを扱う。
再帰的な適用 (関数は目的記述文通りに機能すると想定)
→ あとは必要に応じて値を結合することを検討。
結果値の生成(部分的な結果を結合し最終結果へ):
– 多くの場合、結合は基本処理(+ and consなど)で実現
今回– もし first項のデータに対して何らかのチェックが必要なら
入れ子のcond式が必要なことが考えられる
– 場合により補助関数を導入する必要
例題3. リストが「5」を含むか調べる
1. リストが空ならば： → 基底(再帰的繰返しの終了)
解はfalse
→ 自明な解(要素がなければ5もない)
2. そうでなければ、first部の部分解、 rest部への再帰処理に
よる部分解、これら部分解から最終解の生成を考える：
• リストの first が 5 なら true (最終解)。そうでなければ
rest部（これもリスト）を調べた結果が全体の解になる。
．．．
．．．
first部
は5か?
そうでなければrest 部を調べる(再帰的繰返し)
ここに場合分けがあるのでリストが非空の場合は条件式
例題3. リストが「5」を含むか調べる
(empty? a_list)
Yes
No
(cond
[(= (first a_list) 5) true]
[else (contains-5? (rest a_list))])
(= (first a_list) 5)
No
Yes
false が解
true が解
再帰
(contains-5?
(rest a_list))
例題3. リストが「5」を含むか調べる
contains-5? 関数
;; contains-5?: list -> true or false
;; it investigates whether 5 is included
;; (contains-5? (list 3 5 7 9)) = true
(define (contains-5? a_list)
(cond
最後まで調べた
自明な解
[(empty? a_list) false]
[else
(cond
探索成功
[(= (first a_list) 5) true]
[else (contains-5? (rest a_list))])]))
未発見→最後まで調べてないので再帰的に探索
→ contains-5? の実行が繰り返される
例： (contains-5? (list 3 5 7 9))
= (contains-5? (list 5 7 9))
C言語でcontains-5?
#define SUCCESS 1
#define FAILURE 0
typedef struct _node{
int data;
struct _node *next;
}node_t;
// contains: node_t * -> int
int contains_5(node_t *p){
while (p != NULL) {
if (p->data == 5)
return SUCCESS;
p=p->next;
}
return FAILURE;
}
// contains: node_t * -> int
int contains_5(node_t *p){
if (p == NULL) return FAILURE;
if (p->data == 5) return SUCCESS;
else return contains(p->next, d);
}
再帰での
今日の課題
課題1．勤務時間リストから賃金リストを生成
• まず時間に対する賃金を求める関数 wage を作る
– 賃金＝ 12ドル×勤務時間
• 全従業員の勤務時間のリスト lon から賃金のリスト
を生成する関数 hours->wages を作る
– このとき上記の関数 wage を使う
hours->wages
入力は勤務時
間(数値)のリスト
(list 5 3 6)
出力は賃金
(数値)のリスト
(list 60 36 72)
課題2. 平均点
点数のリストから，平均点を求めるプログラム
average を作り，実行する
– 合計を求める関数 list-sum (練習1)と，リストの長
さを求める関数 how-many (例題2)を組み合わせる
平均点＝
リスト中の点数の総和／リストの要素数
※ リストの要素数が0の時は，0を返すこと
課題3. シンボル出現の判定
シンボルのリスト los と，シンボル a_symbol を入力と
し， los が a_symbol を含むときに限り true を返す
関数 contains? を作りなさい。
参考：例題3 ただし先頭要素との比較対象は5と決まって
いるわけでなく a_symbolとして与えられる。
contains?
入力はリスト
とシンボル
例：
(list 'hi 'bye) と 'bye
→
(list 'day 'night) と 'noon →
出力はブール値
(trueかfalse)
true
false
課題4. 要素の属性を調べる
リストの要素が「偶数」かどうか調べる以下の2つ
の関数を作る：
–
ある要素が偶数なら(偶数を1つでも含めば) true．
1つも含まなければ false を返す関数
–
すべての要素が偶数なら true．1つでも偶数でな
いなら false を返す関数
even? を使うこと

Download Report