5. 任意長の合成データ：リスト プログラミング論I

本日の内容 リスト：有限だが不定数の要素を持つ (参考：構造体は要素数が確定している) 2. Scheme プログラムでのリストの記法 事前に要素数を確定できないデータを処理する場合 2. Scheme プログラムでのリストの記法 リスト関連：cons list first rest empty? list? 任意数の要素を含むリストの再帰的データ定義 リストを処理する再帰的な関数の設計法

リストとは 不定数のデータの並び(合成データ) データの並びには順序があり操作は先頭側から 23, 32, 6, 8 の順にリストに加える例 要素を加えだんだん長く 終端 8 6 32 23 最初は空 23を加える 32を加える 同様に続く… 終端側：先に加えた要素はこちら側 先頭側：後から加えた側。操作はこちらから

リストの作成：cons 空リスト emptyから始め cons を用いてリストを作成 (cons 追加する先頭要素 追加されるリスト) … 8 6 32 23 最初は空 23を加える 32を加える 同様に…

Scheme でのリストの記法 consを使うリストの表記 (長くて見にくい?) listを使った省略記法(以降の説明ではこの記法) (cons 8 (cons 6 (cons 32 (cons 23 empty))) 終端 8 6 32 23 listを使った省略記法(以降の説明ではこの記法) (list 8 6 32 23) 要素データの並び これ自体が1つのデータ値(式) 合成データなので複数の要素データを含み得る

C言語でのリストのプログラム 8 6 NULL data *next 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); #include <stdio.h> #include <stdlib.h> typedef struct _node{ int data; struct _node *next; }node_t; Schemeでは，上記を以下のように書ける 　　(list 8 6 32 23)

C言語でのリストのプログラム 8 6 NULL data *next Schemeでは，上記を以下のように書ける 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); printList(p); 8 6 NULL data *next #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; Schemeでは，上記を以下のように書ける (list 8 6 32 23)

C言語でのリストのプログラム 8 6 NULL data *next Schemeでは，上記を以下のように書ける 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); append(8, &p); printList(p); 8 6 NULL data *next #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; Schemeでは，上記を以下のように書ける (list 23 32 6 8)

リスト要素の参照：first と rest (構造体は定義に応じたフィールドのセレクタで要素参照) 15 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 (rest (list 8 6 32 23)))) = (first (rest (list 6 32 23))) = (first (list 32 23)) = 32 first部 rest部 first部 rest部 first部 rest部 first部 rest部 実行結果

特別なリストemptyとリスト処理のエラー (数でいう 0 のようなもの) 「(空でない)非空のリスト」だけ firstやrest が実行できる。 empty はリストだが要素参照はできない。 演算 非空リスト 空リスト empty リスト以外(数など) first OK 実行エラー rest

データの属性判定：list? empty? 演算と対象データの組合わせによってはエラーに! → 適切な属性判定により正しく処理を進行 「リスト」ならば 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, 2, 3 の順に数が並ぶリスト Lを書け 前述1のリスト Lの先頭に0を加える式を書け 前述1のリスト Lのrest の rest の first を求めよ。それは何番目の要素か? 次の組合せの結果を書け(「エラー」ならエラーと記入) L=(list 1) の場合 L=(list 1 2) L=(list 1 2 3) (first L) の結果 (rest L) (first (rest L))

リストの再帰的データ定義と 再帰的なリスト処理関数の設計法

任意長であるリストの再帰的データ定義 リスト：不定要素数を含む合成データ 要素数を固定しない場合の定義は? →再帰 整数リストの例：すべての整数リストは以下のどちらか * 最初の空リスト (空リストから開始して，より長いリストを構築) * 整数と，他の整数リストを用いて作られた整数リスト 整数リスト 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) (cond [(empty? a_list) …] [else … (first a_list) … … (fun-for-list (rest a_list)) …])) セレクタrestの結 果値へ自己適用 (先頭をとった残りの リストを繰返し処理) 要素がなければ繰り返さない データ定 義と同様 2つの節

リスト処理の再帰関数の本体定義 まず基底ケース(再帰を含まないcond節)から開始 通常、対応する答えは定式化が容易か、あるいは例により既知。 次に自己参照のケースを扱う。 再帰的な適用 (関数は目的記述文通りに機能すると想定) → あとは必要に応じて値を結合することを検討。 結果値の生成(部分的な結果を結合し最終結果へ): 多くの場合、結合は基本処理(+ and consなど)で実現 もし first項のデータに対して何らかのチェックが必要なら 　入れ子のcondが必要なことが考えられる． 場合により補助関数を導入することも必要．

例題2. リストの長さ(要素数) 整数リストの要素数を求める関数 how-many 入力はリスト ： 任意長の再帰データ how-many 出力 数 例：2 整数のリスト 例：(list 11 12) 入力はリスト ： 任意長の再帰データ

リスト処理の再帰関数のテンプレート リスト処理関数のテンプレート 2つの節と1つの矢印を持つcond式を持つ(テキスト表現では矢印の代わりにセレクタ式への関数の自己適用) 整数のリストを処理する関数のテンプレート例 (define (fun-for-loi a_loi) (cond [(empty? a_loi) …] [else … (first a_loi) … … (fun-for-loi (rest a_loi)) …])) セレクタrestの結 果値へ自己適用 (先頭をとった残りの リストを繰返し処理) 要素がなければ繰り返さない データ定 義と同様 2つの節

リスト処理の再帰関数の本体定義 例：関数 how-many (整数リストの要素数を計算する) 基底ケースの答は0 (空リストの要素数は0) ;; 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を加えるだけ： (cond [(empty? a_loi) 0] [else (+ 1 (how-many (rest a_loi)))])) テンプレート

例題2. リストの長さ(要素数) リストが空ならば： → 基底(再帰的繰返しの終了) 解は 0 → 自明な解(要素がないので個数0) リストが空ならば：　→　基底(再帰的繰返しの終了)　 解は 0 →　自明な解(要素がないので個数0) そうでなければ、first部の部分解、 rest部への再帰処理による部分解、これら部分解から最終解の生成を考える：　 リストの rest （これもリスト）の長さに1を足したものが解 ．．． ．．． first部は 要素数1 rest 部の要素数を求める(再帰的繰返し) 足すと全体の要素数になる

例題2. リストの長さ(要素数) 再帰で繰り返し 0 が自明な解である 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 sum=0; while (a_list != NULL){ sum ++; a_list = a_list->next; return sum;

(how-many (list 11 12)) から 2 が得られる過程の概略 = ... =(+ 1 (how-many (list 12))) =(+ 1 (+ 1 (how-many empty))) =(+ 1 (+ 1 0)) =(+ 1 1) =2 (list 11 12)の長さ (list 12)の長さに1を足す empty の長さに1＋1を足す

練習2. 数値リストの要素の和 数値リストの要素を合計する関数list-sumを作れ 出力 入力 数 数のリスト 例：6 練習2. 数値リストの要素の和 数値リストの要素を合計する関数list-sumを作れ 入力 list-sum 出力 数 例：6 数のリスト 例：(list 1 2 3) 入力はリスト ： 任意長の再帰データ テンプレートを使う(how-manyとほぼ同じ) 主な違い：cond式の第2節ではfirst項の要素値とrest項(リスト)に対する部分結果値を合計

例題3. リストが「5」を含むか調べる 入力は 出力はブール値 1つのリスト (trueかfalse) 例題3. リストが「5」を含むか調べる リストの要素の中に「5」を含むかどうか調べる関数 contains-5? を作る。 リスト処理再帰関数のテンプレートを使う contains-5? 入力は 1つのリスト 出力はブール値 (trueかfalse) (list 3 5 7 9) true

リスト処理の再帰関数の本体定義 まず基底ケース(再帰を含まないcond節)から開始 通常、対応する答えは定式化が容易か、あるいは例により既知。 次に自己参照のケースを扱う。 再帰的な適用 (関数は目的記述文通りに機能すると想定) → あとは必要に応じて値を結合することを検討。 結果値の生成(部分的な結果を結合し最終結果へ): 多くの場合、結合は基本処理(+ and consなど)で実現 もし first項のデータに対して何らかのチェックが必要なら 入れ子のcond式が必要なことが考えられる 場合により補助関数を導入する必要 今回

例題3. リストが「5」を含むか調べる リストが空ならば： → 基底(再帰的繰返しの終了) 例題3. リストが「5」を含むか調べる リストが空ならば：　→　基底(再帰的繰返しの終了)　 解はfalse →　自明な解(要素がなければ5もない) そうでなければ、first部の部分解、 rest部への再帰処理による部分解、これら部分解から最終解の生成を考える： 　 リストの first が 5 なら true (最終解)。そうでなければ rest部（これもリスト）を調べた結果が全体の解になる。 ．．． ．．． first部 は5か? そうでなければrest 部を調べる(再帰的繰返し) ここに場合分けがあるのでリストが非空の場合は条件式

例題3. リストが「5」を含むか調べる No (empty? a_list) Yes No Yes 再帰 false が解 true が解 例題3. リストが「5」を含むか調べる No (empty? a_list) (cond [(= (first a_list) 5) true] [else (contains-5? (rest a_list))]) Yes No (= (first a_list) 5) 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 [(= (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){ if (p == NULL) return FAILURE; if (p->data == 5) return SUCCESS; else return contains(p->next, d); } // contains: node_t * -> int int contains_5(node_t *p){ while (p != NULL) { if (p->data == 5) return SUCCESS; p=p->next; } return FAILURE; 再帰での

今日の課題

課題1．勤務時間リストから賃金リストを生成 まず時間に対する賃金を求める関数 wage を作る 賃金　＝　12ドル×勤務時間 全従業員の勤務時間のリスト lon から賃金のリストを生成する関数 hours->wages を作る このとき上記の関数 wage を使う hours->wages 入力は勤務時 間(数値)のリスト 出力は賃金 (数値)のリスト (list 60 36 72) (list 5 3 6)

課題2. 平均点 点数のリストから，平均点を求めるプログラム average を作り，実行する 平均点 ＝ 合計を求める関数 list-sum (練習1)と，リストの長さを求める関数 how-many (例題2)を組み合わせる 平均点 ＝ リスト中の点数の総和 ／ リストの要素数 ※ リストの要素数が0の時は，0を返すこと

課題3. シンボル出現の判定 シンボルのリスト los と，シンボル a_symbol を入力とし， los が a_symbol を含むときに限り true を返す関数 contains? を作りなさい。 参考：例題3 ただし先頭要素との比較対象は5と決まっているわけでなく a_symbolとして与えられる。 contains? 入力はリスト とシンボル 出力はブール値 (trueかfalse) 例： (list 'hi 'bye) と 'bye → true (list 'day 'night) と 'noon → false

課題4. 要素の属性を調べる リストの要素が 「偶数」かどうか調べる以下の2つの関数を作る： ある要素が偶数なら(偶数を1つでも含めば) true．1つも含まなければ false を返す関数 すべての要素が偶数なら true．1つでも偶数でないなら false を返す関数 even? を使うこと