sp-6. リストと繰り返し処理

sp-6. リストと繰り返し処理 （Scheme プログラミング） URL: https://www.kkaneko.jp/pro/scheme/index.html 金子邦彦 1

• https://www.kkaneko.jp/pro/scheme/index.html

アウトライン 6-1 リストと繰り返し処理 6-2 パソコン演習 6-3 課題 2

本日の内容 1. リストを扱う関数の書き方について • 再帰 • cond 文との組み合わせ • リストの要素に対する繰り返し処理 2. 再帰を使ったプログラムに慣れ，自力で読み書 きできるようになる 3

リストと繰り返し処理 リストを扱うプログラムでは リストの要素の数だけ， 同じ処理を繰り返す ことが多い • 長さが１０のリストなら，処理を１０回繰り返 したい ⇒ 「再帰」のテクニック（次ページ） 4

再帰 再帰関数のパターン (define (foo パラメータの並び) (cond [終了条件 自明の答] [else (foo 新たなパラメータの並び)])) • 関数(上では foo)の内部に ，同じ関数 foo が登場 • foo の実行が繰り返される 5

再帰での終了条件 (define (foo ...) (cond [終了条件 自明の答] [else (foo 新たなパラメータ)])) 終了条件 No Yes 再帰呼び出し 自明な解 • 条件文（cond） と組み合わせ • 繰り返しのたびに 「終了条件」の真偽が判定される • 「終了条件」が満足されるまで ，処理が繰り返される 6

リストでの繰り返しと終了条件 • ある終了条件（例えば、リストが empty に なるなど）が満足されたら，処理を終える • リストの rest をとりながら，処理を繰り返 すことが多い 7

パソコン演習 8

パソコン演習の進め方 • 資料を見ながら，「例題」を行ってみる • 各自，「課題」に挑戦する • 自分のペースで先に進んで構いません 9

DrScheme の使用 • DrScheme の起動 プログラム • → PLT Scheme → DrScheme 今日の演習では「Intermediate Student」 に設定 Language → Choose Language → Intermediate Student → Execute ボタン 10

例題１．リストの総和 数のリスト a-list から総和を求める関数 listsum を作り，実行する • • x1, x2, … , xn のリストに対して，総和 x1 + x2 + … + xn を求める 11

「例題１．リストの総和」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) 2. その後，次を「実行用ウインドウ」で実行しなさい (sum (list 1 2 3)) (sum (list 11 12 13)) ☆ 次は，例題２に進んでください 12

まず，Scheme のプログラムを コンピュータに読み込ませている 13

これは， (list-sum (list 1 2 3)) と書いて，a-list の値を (list 1 2 3) に設定しての実行 実行結果である「6」が 表示される 14

入力と出力 6 (list 1 2 3) list-sum 入力は １つのリスト 出力は １つの数値 15

list-sum 関数 「関数である」ことを 示すキーワード 関数の名前 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) 値を1つ受け取る（入力） a-list の値から リストの総和を求める（出力） 16

リストの総和 1. リストが空ならば： 0 → 終了条件 → 自明な解 2. そうで無ければ： • リストの rest を求める（これもリスト）． 「その総和と，リストの先頭との和」が， 求める総和である 17

リストの総和 リストが空で無いとき 総和を求める ．．． first ．．． rest 総和を求める ．．． ．．． （それを，リストの first と足す） 18

リストの総和 (define (list-sum a-list) (cond 終了条件 [(empty? a-list) 0]自明な解 [else (+ (first a-list) (list-sum (rest alist)))])) 19

No (empty? a-list) Yes (+ (first a-list) (list-sum (rest a-list))) 0 が自明な解である 20

リストの総和 list-sum • list-sum の内部に list-sum が登場 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) • sum の実行が繰り返される 例： (list-sum (list 1 2 3)) = (+ 1 (list-sum (list 2 3))) 21

例題２．ステップ実行 • 関数 list-sum （例題１）について，実行結果 に至る過程を見る • (list-sum (list 1 2 3)) から 6 に至る過程を見る • DrScheme の stepper を使用する = (list-sum (list 1 2 3)) = ... = (+ 1 (list-sum (list 2 3))) = ... = (+ 1 (+ 2 (list-sum (list 3)))) = ... = (+ 1 (+ 2 (+ 3 (list-sum empty)))) = ... = (+ 1 (+ 2 (+ 3 0))) = (+ 1 (+ 2 3)) = (+ 1 5) =6 基本的な計算式 への展開 演算の実行 22

「例題２．ステップ実行」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • Intermediate Student で実行すること • 入力した後に，Execute ボタンを押す (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) (list-sum (list 1 2 3)) 例題１と同じ 2. DrScheme を使って，ステップ実行の様子を 確認しなさい （Step ボタン，Next ボタンを使用） • 理解しながら進むこと ☆ 次は，例題３に進んでください 23

(list-sum (list 1 2 3)) から 6 が得られる過程の概略 = (list-sum (list 1 2 3)) (list 1 2 3) の和 最初の式 = ... = (+ 1 (list-sum (list 2 3))) (list 2 3) の和に1を足す = ... = (+ 1 (+ 2 (list-sum (list 3)))) (list 3) の和に1,2を足す = ... = (+ 1 (+ 2 (+ 3 (list-sum empty)))) emptyの和に1,2,3を足す = ... = (+ 1 (+ 2 (+ 3 0))) = (+ 1 (+ 2 3)) = (+ 1 5) コンピュータ内部での計算 =6 実行結果 24

(list-sum (list 1 2 3)) から (+ 1 (list 2 3)) が得られる過程 (list-sum (list 1 2 3)) = (list-sum (list 1 2 3)) = (cond = ... [(empty? (list 1 2 3)) 0] [else (+ (first (list 1 2 3)) = (+ 1 (list-sum (list 2 3))) (list-sum (rest (list 1 2 3))))]) この部分は = ... = (cond = (+ 1 (+ 2 (list-sum (list 3)))) [false 0] [else (+ (first (list 1 2 3)) = ... (list-sum (rest (list 1 2 3))))]) = (+ (first (list 1 2 3)) = (+ 1 (+ 2 (+ 3 (list-sum empty)))) (list-sum (rest (list 1 2 3)))) = ... = (+ 1 (list-sum (rest (list 1 2 3)))) = (+ 1 (+ 2 (+ 3 0))) = (+ 1 = (+ 1 (+ 2 3)) (list-sum (list 2 3))) = (+ 1 5) =6 25

(list-sum (list 1 2 3)) から (+ 1 (list 2 3)) が得られる過程 (list-sum (list 1 2 3)) = (list-sum (list 1 2 3)) = (cond = ... [(empty? (list 1 2 3)) 0] [else (+ (first (list 1 2 3)) = (+ 1 (list-sum (list 2 3))) (list-sum (rest (list 1 2 3))))]) この部分は = ... = (cond = (+ 1 (+ 2 (list-sum (list 3)))) [false 0] [else (+ (first (list 1 2 3)) = ... (list-sum (rest (list 1 2 3))))]) = (+ (first (list 1 2 3)) = (+これは， 1 (+ 2 (+ 3 (list-sum empty)))) (list-sum (rest (list 1 2 3)))) = ... (define (sum a-list) = (+ 1 (cond (list-sum (rest (list 1 2 3)))) = (+ 1 (+ [(empty? 2 (+ 3 0))) a-list) 0] = (+ 1 = (+ 1 (+ [else 2 3))(+ (first a-list) (list-sum (list 2 3))) (sum (rest a-list)))])) = (+ 1 5) の a-list を (list 1 2 3) で置き換えたもの =6 26

(contains-5? (list 3 5 7 9)) から (contains-5? (list 5 7 9))が得られる過程 (list 3 5 7 9)) (contains-5? (list 3 5 7 9))(contains-5? = (cond [(empty? (list 3 5 7 9)) false] [else (cond =… この部分は [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) =(contains-5? (list 5 7 9)) = (cond [false false] =… [else (cond [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) = これは， true = (cond (define (contains-5? a-list) [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) (cond = (cond [(empty? a-list) false] [(= 3 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) [else (cond = (cond [(= (first a-list) 5) true] [false true] [else (contains-5? (rest (list 3 5 7 9)))]) [else (contains-5? (rest a-list))])])) = (contains-5? (rest (list 3 5 7 9))) の a-list を (list 3 5 7 9) で置き換えたもの = (contains-5? (list 5 7 9)) 27

例題３．平均点 • 点数のリストから，平均点を求めるプログラ ム average を作り，実行する • 点数のデータはリストとして扱う • 合計を求める関数 list-sum と，リストの長さを求 める関数 length を組み合わせる list-sum, length については、以前の授 業の資 料を参照のこと 28

平均点 平均点 ＝ リストの総和／リストの長さ 29

「例題３．平均点」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す ;; list-sum: list -> number ;; total of a list ;; (list-sum (list 40 90 80)) = 210 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) ;; average: list -> number ;; average of a list ;; (average (list 40 90 80)) = 70 (define (average a-list) (/ (list-sum a-list) (length a-list))) 2. その後，次を「実行用ウインドウ」で実行しなさい (average (list 40 90 80)) (average (list 100 200 300 400 500)) ☆ 次は，例題４に進んでください 30

まず，Scheme のプログラムを コンピュータに読み込ませている 31

これは， (average (list 40 90 80)) と書いて，a-list の値を (list 40 90 80) に設定しての実行 実行結果である「70」が 表示される 32

入力と出力 (list 40 90 80) 70 average 入力 入力はリスト 出力 出力は数値 33

平均点のプログラム ;; list-sum: list -> number ;; total of a list ;; (list-sum (list 40 90 80)) = 210 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) ;; average: list -> number ;; average of a list ;; (average (list 40 90 80)) = 70 (define (average a-list) (/ (list-sum a-list) (length a-list))) list-sum の部分 average の部分 34

list-sum, average の関係 • list-sum • 「数のリスト」から「リストの総和」を求める • average • 「数のリスト」から「平均」を求める • list-sum を使用 35

例題４．ステップ実行 • 関数 average （例題３）について，実行結果 に至る過程を見る • (average (list 40 90 80)) から 70 に至る過程を見 る • DrScheme の stepper を使用する (average (list 40 90 80)) = (/ (list-sum (list 40 90 80)) (length (list 40 90 80))) =… = (/ 210 (length (list 40 90 80))) = ... = (/ 210 3) = 70 36

「例題４．ステップ実行」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • Intermediate Student で実行すること • 入力した後に，Execute ボタンを押す ;; list-sum: list -> number ;; total of a list ;; (list-sum (list 40 90 80)) = 210 (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) ;; average: list -> number ;; average of a list ;; (average (list 40 90 80)) = 70 (define (average a-list) (/ (list-sum a-list) (length a-list))) (list-sum (list 40 90 80)) 例題３と同じ 2. DrScheme を使って，ステップ実行の様子を 確認しなさい （Step ボタン，Next ボタンを使用） • 理解しながら進むこと ☆ 次は，例題５に進んでください 37

(average (list 40 90 80)) から 70 が得られる過程の概略 最初の式 (average (list 40 90 80)) = (/ (list-sum (list 40 90 80)) (length (list 40 90 80))) =… = (/ 210 (length (list 40 90 80))) = ... = (/ 210 3) コンピュータ内部での計算 = 70 実行結果 38

(average (list 40 90 80)) から 70 が得られる過程の概略 (average (list 40 90 80)) = (/ (list-sum (list 40 90 80)) (length (list 40 90 80))) =… = (/ 210 (length (list 40 90 80))) これは， = ... (define (average a-list) = (/ 210(/3)(list-sum a-list) (length a-list))) = 70 の a-list を (list 40 90 80) で置き換えたもの 39

例題５．「5」を含むか調べる • リストの要素の中に「5」を含むかどうか調 べる関数 contains-5? を作り，実行する 40

「例題５．「5」を含むか調べる」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す ;; 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))])])) 2. その後，次を「実行用ウインドウ」で実行しなさい (contains-5? (list 1 2 3 4)) (contains-5? (list 3 5 7 9)) ☆ 次は，例題６に進んでください 41

まず，Scheme のプログラムを コンピュータに読み込ませている 42

これは， (contains-5? (list 3 5 7 9)) と書いて，a-list の値を (list 3 5 7 9) に設定しての実行 実行結果である「true」が 表示される 43

入力と出力 true (list 3 5 7 9) contains-5? 入力は １つのリスト 出力は true/false 値 44

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))])])) 45

「5」を含むか調べる 1. リストが空ならば： → 終了条件 false → 自明な解 2. そうで無ければ： • リストの first が「5」であるかを調べ る． • 「5」ならば： true • 「5」で無いならば: リストの rest が「5」 を含むかどうかを調べる 46

「5」を含むか調べる リストが空で無いとき 「5」 を含むか調べる ．．． ．．． first 「5」で無いならば rest 「5」 を含むか調べる ．．． ．．． 47

「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))])])) 48

(empty? a-list) Yes No (cond [(= (first a-list) 5) true] [else (contains-5? (rest a-list))] false が自明な解である 49

「5」を含むか調べる contains-5? • contains-5? の内部に contains-5? が登場 (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)) 50

例題６．ステップ実行 • 関数 contains-5? （例題５）について，実行 結果に至る過程を見る • (contains-5? (list 3 5 7 9)) から true に至る過程 を見る • DrScheme の stepper を使用する (contains-5? (list 3 5 7 9)) =… =(contains-5? (list 5 7 9)) =… = true 51

「例題６．ステップ実行」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • • Intermediate Student で実行すること 入力した後に，Execute ボタンを押す (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? (list 3 5 7 9)) 例題５と同じ 2. DrScheme を使って，ステップ実行の様子を 確認しなさい （Step ボタン，Next ボタンを使用） • 理解しながら進むこと ☆ 次は，例題７に進んでください 52

(contains-5? (list 3 5 7 9)) から true が得られる過程の概略 (contains-5? (list 3 5 7 9))最初の式 (list 3 5 7 9) から探す =… =(contains-5? (list 5 7 9)) =… (list 5 7 9) から探す コンピュータ内部での計算 = true 実行結果 先頭が 5 なので true 53

(contains-5? (list 3 5 7 9)) から (contains-5? (list 5 7 9))が得られる過程 (list 3 5 7 9)) (contains-5? (list 3 5 7 9))(contains-5? = (cond =… =(contains-5? (list =… = true [(empty? (list 3 5 7 9)) false] [else (cond この部分は [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) 5 7 9)) = (cond [false false] [else (cond [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) = (cond [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) = (cond [(= 3 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) = (cond [false true] [else (contains-5? (rest (list 3 5 7 9)))]) = (contains-5? (rest (list 3 5 7 9))) = (contains-5? (list 5 7 9)) 54

(contains-5? (list 3 5 7 9)) から (contains-5? (list 5 7 9))が得られる過程 (list 3 5 7 9)) (contains-5? (list 3 5 7 9))(contains-5? = (cond [(empty? (list 3 5 7 9)) false] [else (cond =… この部分は [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) =(contains-5? (list 5 7 9)) = (cond [false false] =… [else (cond [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))])]) = これは， true = (cond (define (contains-5? a-list) [(= (first (list 3 5 7 9)) 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) (cond = (cond [(empty? a-list) false] [(= 3 5) true] [else (contains-5? (rest (list 3 5 7 9)))]) [else (cond = (cond [(= (first a-list) 5) true] [false true] [else (contains-5? (rest (list 3 5 7 9)))]) [else (contains-5? (rest a-list))])])) = (contains-5? (rest (list 3 5 7 9))) の a-list を (list 3 5 7 9) で置き換えたもの = (contains-5? (list 5 7 9)) 55

例題７．ベクトルの内積 • ２つのベクトルデータ x, y から２つのベクトル の内積を求めるプログラム product を作り，実 行する • ２つのベクトルデータ x, y はリストとして扱う 56

「例題７．ベクトルの内積」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • 入力した後に，Execute ボタンを押す ;; product: list list -> number ;; inner product of two vectors ;; (product (list 1 2 3) (list 4 5 6)) = 32 (define (product x y) (cond [(empty? x) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) 2. その後，次を「実行用ウインドウ」で実行しなさい (product (list 1 2 3) (list 4 5 6)) ☆ 次は，例題８に進んでください 57

まず，Scheme のプログラムを コンピュータに読み込ませている 58

これは， (product (list 1 2 3) (list 4 5 6)) と書いて，x の値を(list 1 2 3) に， y の値を (list 4 5 6) に設定しての実行 実行結果である「32」が 表示される 59

入力と出力 (list 1 2 3) (list 4 5 6) 32 product 入力 入力は， ２つのリスト 出力 出力は数値 60

product 関数 ;; product: list list -> number ;; inner product of two vectors ;; (product (list 1 2 3) (list 4 5 6)) = 32 (define (product x y) (cond [(empty? x) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) 61

よくある勘違い (define (product x y) (cond [(= x empty) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) 終了条件の判定： ・ 正しくは「(empty? x)」 ・ x がリストのとき、(= x empty) はエラー ・ 「=」は数値の比較には使えるが，リスト同士の比較に は使えない 62

ベクトルの内積 1. リストが空ならば： 0 → 終了条件 → 自明な解 2. そうで無ければ： – 「２つのリストの rest の内積と，２つの リストの先頭の積との和」 が求める解 63

ベクトルの内積 ;; product: list list -> number ;; inner product of two vectors ;; (product (list 1 2 3) (list 4 5 6)) = 32 (define (product x y) 終了 条件 (cond [(empty? x) 0] 自明な解 [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) 64

No (empty? x) Yes (+ (* (first x) (first y)) (product (rest x) (rest y))) 0 が自明な解である 65

ベクトルの内積 product • product の内部に product が登場 (define (product x y) (cond [(empty? x) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) • product の実行が繰り返される 例： (product (list 1 2 3) (list 4 5 6)) = (+ (* 1 4) (product (list 2 3) (list 5 6))) 66

例題８．ステップ実行 • 関数 product （例題７）について，実行結果に至 る過程を見る • (product (list 1 2 3) (list 4 5 6)) から 32 に至る過程を見 る • DrScheme の stepper を使用する (product (list 1 2 3) (list 4 5 6)) =… = (+ (* 1 4) (product (list 2 3) (list 5 6))) =… 基本的な計算式 = (+ 4 への展開 (+ 10 (product (list 3) (list 6)))) =… = (+ 4 (+ 10 (+ 18 (product empty empty)))) =… 演算の実行 = 32 67

「例題８．ステップ実行」の手順 1. 次を「定義用ウインドウ」で，実行しなさい • • Intermediate Student で実行すること 入力した後に，Execute ボタンを押す (define (product x y) (cond [(empty? x) 0] [else (+ (* (first x) (first y)) (product (rest x) (rest y)))])) (product (list 1 2 3) (list 4 5 6)) 例題７と同じ 2. DrScheme を使って，ステップ実行の様子を 確認しなさい （Step ボタン，Next ボタンを使用） • 理解しながら進むこと ☆ 次は，課題に進んでください 68

(product (list 1 2 3) (list 4 5 6)) から 32 が得られる過程の概略 最初の式 (product (list 1 2 3) (list 4 5 6)) =… = (+ (* 1 4) (product (list 2 3) (list 5 6))) =… = (+ 4 (+ 10 (product (list 3) (list 6)))) =… = (+ 4 (+ 10 (+ 18 (product empty empty)))) コンピュータ内部での計算 =… 実行結果 = 32 69

(product (list 1 2 3) (list 4 5 6)) から (+ 4 (product (list 2 3) (list 5 6))) が得られる過程 (product (list 1 2 3) (list 4 5 6)) = (cond (product (list 1 2 3) (list 4 5 6)) [(empty? (list 1 2 3)) 0] [else (+ (* (first (list 1 2 3)) (first (list 4 5 6))) =… (product (rest (list 1 2 3)) (rest (list 4 5 6))))]) この部分は = (cond = (+ 4 [false 0] (* (first (list 1 2 3)) (first (list 4 5 6))) (product (list 2 3) (list 5 6))) [else (+(product (rest (list 1 2 3)) (rest (list 4 5 6))))]) = (+ (* (first (list 1 2 3)) (first (list 4 5 6))) =… (product (rest (list 1 2 3)) (rest (list 4 5 6)))) = (+ (* 1 (first (list 4 5 6))) = (+ 4 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) = (+ (* 1 4) (+ 10 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) (product (list 3) (list 6)))) = (+ 4 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) = (+ 4 (product (list 2 3) (rest (list 4 5 6)))) =… = (+ 4 (product (list 2 3) (list 5 6))) = (+ 4 (+ 10 (+ 18 (product empty empty)))) =… = 32 70

(product (list 1 2 3) (list 4 5 6)) から (+ 4 (product (list 2 3) (list 5 6))) が得られる過程 (product (list 1 2 3) (list 4 5 6)) = (cond (product (list 1 2 3) (list 4 5 6)) [(empty? (list 1 2 3)) 0] [else (+ (* (first (list 1 2 3)) (first (list 4 5 6))) =… (product (rest (list 1 2 3)) (rest (list 4 5 6))))]) この部分は = (cond = (+ 4 [false 0] (* (first (list 1 2 3)) (first (list 4 5 6))) (product (list 2 3) (list 5 6))) [else (+(product (rest (list 1 2 3)) (rest (list 4 5 6))))]) = (+ (* (first (list 1 2 3)) (first (list 4 5 6))) =… (product (rest (list 1 2 3)) (rest (list 4 5 6)))) これは， = (+ (* 1 (first (list 4 5 6))) = (+ 4 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) (define (product x y) = (+ (* 1 4) (+ 10 (cond (product (rest (list 1 2 3)) (rest (list 4 5 6)))) (product (list 3) [(empty? x) (list 0] 6)))) = (+ 4 (product (rest (list 1 2 3)) (rest (list 4 5 6)))) = (+ 4 (product (list 2 3) (rest (list 4 5 6)))) [else (+ (* (first x) (first =y)) =… (+ 4 (product (list 2 3) (list 5 6))) (product (rest x) (rest y)))])) = (+ 4 (+ 10 (+ 18 (product empty empty)))) の x を (list 1 2 3) で，y を (list 4 5 6) で置き換えたもの =… = 32 71

今日のパソコン演習課題 72

課題１ • 関数 list-sum （授業の例題１）についての問 題 • (list-sum (list 1 2 3)) から 6 が得られる過程の概略 を数行程度で説明しなさい • DrScheme の stepper を使うと，すぐに分かる (define (list-sum a-list) (cond [(empty? a-list) 0] [else (+ (first a-list) (list-sum (rest a-list)))])) 73

課題２ DrScheme の stepper を利用した実行エラーの解決 に関する問題 1. まずは，次を「定義用ウインドウ」で，実行しなさい – 入力した後に，Execute ボタンを押す ⇒ すると，実行用ウインドウに（赤い文字で）エラーメッ セージが表示される（これは実行エラー） (define (list-length a-list) (cond [(empty? a-list) 0] [else (+ 1 (list-length (rest a-list)))])) (list-length 100) 2. DrScheme で stepper を使ってステップ実行を行って， エラーの箇所を特定しなさい．エラーの原因について 報告しなさい． 74

課題３ シンボル出現の判定プログラム作成 • シンボルのリスト a-list と，シンボル a-symbol から，a-list が a-symbol を含むときに限り true を返す関数 contains? を作りなさい 75

課題３のヒント： すべての要素が１０以上か？ • リストの要素を調べ， • すべての要素が１０以上 → true • そうでなければ → false (define (all-are-large alon) (cond [(empty? alon) true] [else (and (<= 10 (first alon)) (all-are-large (rest alon)))])) 76

課題４ • リストの要素の中に 「偶数」を含むかどう か調べる関数を作りなさい • 偶数を１つでも含めば true．１つも含まなけれ ば false • even? を使うこと 77

課題５ • n次の多項式 f(x) = a0 + a1・x + a2・x２+ ・・・ +anｎ・x について，次数 n と，係数 a0 から an から，f(x) を計算するプログラムを作りなさい • 次ページ以降で説明する Horner法を使うこと 78

多項式の計算 • n次の多項式 f(x) = a0 + a1・x + a2・x2 + ・・・ +an・xn について，次数 n ，係数 a0 から an と x か らf(x) を計算する 79

Horner法による多項式の計算 f(x) n = a0 + a1・x + a2・x2 + ・・・ +an・x = a0 + ( a1 + ( a2 + ・・・ + ( an-1 + an ・x ) x ・・・) x ) x 例えば， 5 + 6x + 3x = 5 + ( 6 + 3x2) x 計算手順 ① an ② an-1 + an・x ③ an-2 + ( an-1 + an・x ) x ・・・ （a0 まで続ける） 80

さらに勉強したい人への 補足説明資料 81

リストに関係する関数 • (length list) リストの要素の個数 • (list-ref list n) リストのｎ番目の要素（先頭は０番目） これらの関数と同じ機能を持つ関数 my-length, my-list-ref を敢えて書いて みた例を以下に紹介する 82

例題９．リストの n 番目の要素 • リストの n 番目の要素（先頭は 0 番 目）を得る関数 my-list-ref を作り， 実行する 83

まず，Scheme のプログラムを コンピュータに読み込ませている 84

これは， (my-list-ref (list 11 12 13 14) 1) と書いて，a-list の値を (list 11 12 13 14) に, n の値を 1 に設定しての実行 実行結果である「12」が 表示される 85

入力と出力 (list 11 12 13 14) 1 12 my-list-ref 入力 出力 86

my-list-ref 関数 「関数である」ことを 示すキーワード 関数の名前 (define (my-list-ref a-list n) (cond [(= n 0) (first a-list)] [else (my-list-ref (rest a-list) (- n 1))])) 値を2つ受け取る（入力） a-list と n の値から n 番目の要素を求める（出力） 87

(my-list-ref (list 11 12 13 14) 1) から12が得られる過程 (my-list-ref (list 11 12 13 14) 1) 最初の式 = (cond [(= 1 0) (first (list 11 12 13 14))] [else (my-list-ref (rest (list 11 12 13 14) ) (- 1 1))]) = (cond [false (first (list 11 12 13 14))] [else (my-list-ref (rest (list 11 12 13 14) ) (- 1 1))]) = (my-list-ref (rest (list 11 12 13 14) ) (- 1 1)) = (my-list-ref (list 12 13 14) (- 1 1)) = (my-list-ref (list 12 13 14) 0) = (cond [(= 0 0) (first (list 12 13 14))] [else (my-list-ref (rest (list 12 13 14) ) (- 0 1))]) = (cond [true (first (list 12 13 14))] [else (my-list-ref (rest (list 12 13 14) ) (- 0 1))]) コンピュータ内部での計算 = (first (list 12 13 14)) 88 = 12 実行結果

(my-list-ref (list 11 12 13 14) 1) から12が得られる過程 (my-list-ref (list 11 12 13 14) 1) = (cond [(= 1 0) (first (list 11 12 13 14))] [else (my-list-ref (rest (list 11 12 13 14) ) (- 1 1))]) = (cond [false (first (list 11 12 13 14))] [else (my-list-ref (rest (list 11 12 13 14) ) (- 1 1))]) これは， = (my-list-ref (rest (list 11 12 13 14) ) (- 1 1)) (define (list (my-list-ref a-list = (my-list-ref 12 13 14) (1 1))n) = (my-list-ref (cond(list 12 13 14) 0) = (cond [(= n 0) (first a-list)] [(= 0 0) (first (list 12 13 14))] [else (my-list-ref 1))])) [else (my-list-ref (rest (list(rest 12 13a-list) 14) ) (-(-0 n 1))]) =の (cond a-list を (list 11 12 13 14) で，n を 1 で置き換えたも の [true (first (list 12 13 14))] [else (my-list-ref (rest (list 12 13 14) ) (- 0 1))]) = (first (list 12 13 14)) 89 = 12

(my-list-ref (list 11 12 13 14) 1) から 12が得られる過程の概略 (my-list-ref (list 11 12 13 14) 1) =… = (my-list-ref (list 12 13 14) 0) = … = (first (list 12 13 14)) = 12 リストの1番目 の要素 リスト rest を取って， その0番目の要素 リストの先頭 90

my-list-ref の「a-list」は「(list 11 12 13 14)」で 「n」は「1」で置き換わる 91

「(= 1 0)」 は 「false」で置き換わる 92

「(cond [false 式Ｘ] [else 式Ｙ])」は 「式Ｙ」で置き換わる 93

「(rest (list 11 12 13 14))」は 「(list 12 13 14)」で置き換わる 94

「(- 1 1)」は「0」で置き換わる 95

my-list-ref の「a-list」は「(list 12 13 14)」で， 「n」は「0」で置き換わる 96

「(= 0 0)」 は 「true」で置き換わる 97

「(cond [true 式Ｘ] [else 式Ｙ])」は 「式Ｘ」で置き換わる 98

「(first (list 12 13 14))」は 「12」で置き換わる 99

リストの n 番目の要素 1. n = 0 ならば： → 終了条件 リストの first → 自明な解 2. そうで無ければ： – 「リストの rest を求める（これもリ スト）．その n-1 番目の要素」が求 める解 100

リストの n 番目の要素 n > 0 のとき n 番目を探す ．．． first ．．． rest n-1 番目を探す ．．． ．．． 101

リストの n 番目の要素 (define (my-list-ref a-list n) (cond 終了 [(= n 0) (first a-list)] 自明な解 条件 [else (my-list-ref (rest a-list) (- n 1))])) 102

(= n 0) No Yes (my-list-ref (rest a-list) (- n 1)) (first a-list) が自明な解である 103

リストの n 番目の要素 my-list-ref • my-list-ref の内部に my-list-ref が登場 (define (my-list-ref a-list n) (cond [(= n 0) (first a-list)] [else (my-list-ref (rest a-list) (- n 1))])) • my-list-ref の実行が繰り返される 例： (my-list-ref (list 11 12 13 14) 1) = (my-list-ref (list 12 13 14) 0) 104

例題１０．リストの長さ • リストの要素の個数を求める関数 my-length を作り，実行する 105

まず，Scheme のプログラムを コンピュータに読み込ませている 106

これは， (my-length (list 11 12)) と書いて，a-list の値を (list 11 12) に設定しての実行 実行結果である「2」が 表示される 107

入力と出力 2 (list 11 12) my-length 入力 出力 108

my-length 関数 「関数である」ことを 示すキーワード 関数の名前 (define (my-length a-list) (cond [(empty? a-list) 0] [else (+ 1 (my-length (rest a-list)))])) 値を1つ受け取る（入力） a-list の値から リストの長さを求める（出力） 109

(my-list-ref (list 11 12)) から 2 が得られる過程 (1/2) (my-length (list 11 12)) 最初の式 = (cond [(empty? (list 11 12)) 0] [else (+ 1 (my-length (rest (list 11 12))))]) = (cond [false 0] [else (+ 1 (my-length (rest (list 11 12))))]) = (+ 1 (my-length (rest (list 11 12)))) = (+ 1 (my-length (list 12))) = (+ 1 (cond [(empty? (list 12)) 0] [else (+ 1 (my-length (rest (list 12))))])) = (+ 1 (cond [false 0] [else (+ 1 (my-length (rest (list 12))))])) コンピュータ内部での計算 110

(my-list-ref (list 11 12)) から 2 が得られる過程 (2/2) = (+ 1 (+ 1 (my-length (rest (list 12))))) = (+ 1 (+ 1 (my-length empty))) = (+ 1 (+ 1 (cond [(empty? empty) 0] [else (+ 1 (my-length empty))])) = (+ 1 (+ 1 (cond [true 0] [else (+ 1 (my-length empty))])) = (+ 1 (+ 1 0)) コンピュータ内部での計算 = (+ 1 1) =2 実行結果 111

(my-length (list 11 12)) から 2 が得られる過程の概略 (my-length (list 11 12)) (list 11 12) の長さ = ... = (+ 1 (my-length (list 12))) (list 12) の長さに１を足す = ... = (+ 1 (+ 1 (my-length empty))) empty の長さに２を足す = ... = (+ 1 (+ 1 0)) = (+ 1 1) =2 112

よくある勘違い (define (my-length a-list) (cond [(= a-list empty) 0] [else (+ 1 (my-length (rest a-list)))])) 終了条件の判定： ・ 正しくは「(empty? a-list)」 ・ x がリストのとき、(= x empty) は実行エラー ・ 「=」は数値の比較には使えるが，リスト同士の比較に は使えない 113

実行エラーの例 114

リストの長さ 1. リストが空ならば： 0 → 終了条件 → 自明な解 2. そうで無ければ： • リストの rest を求める（これもリスト）． 「その長さに１を足したもの」が，求め る総和である 115

リストの長さ リストが空で無いとき 長さを求める ．．． first ．．． rest 長さを求める ．．． ．．． （それを１ と足す） 116

リストの長さ (define (my-length a-list) (cond 終了条件 [(empty? a-list) 0] 自明な解 [else (+ 1 (my-length (rest a-list)))])) 117

No (empty? a-list) Yes (+ 1 (my-length (rest a-list))) 0 が自明な解である 118

リストの長さ my-length • my-length の内部に my-length が登場 (define (my-length a-list) (cond [(empty? a-list) 0] [else (+ 1 (my-length (rest a-list)))])) • my-length の実行が繰り返される 例： (my-length (list 11 12)) = = (+ 1 (my-length (list 12))) 119