アウトライン
6-1 リストと繰り返し処理
6-2 パソコン演習
6-3 課題
2
1. リストを扱う関数の書き方について
•再帰
•cond 文との組み合わせ
•リストの要素に対する繰り返し処理
2. 再帰を使ったプログラムに慣れ，自力で読み書
きできるようになる
本日の内容
3
リストの要素の数だけ，
同じ処理を繰り返す
リストを扱うプログラムでは
ことが多い
•長さが１０のリストなら，処理を１０回繰り返
したい
⇒「再帰」のテクニック（次ページ）
リストと繰り返し処理
4
(define (foo パラメータの並び)
(cond
[終了条件 自明の答]
[else (foo 新たなパラメータの並び)]))
•関数(上では foo)の内部に ，同じ関数 foo
が登場
•foo の実行が繰り返される
再帰関数のパターン
再帰
5
•条件文（cond） と組み合わせ
•繰り返しのたびに 「終了条件」の真偽が判定される
•「終了条件」が満足されるまで ，処理が繰り返される
(define (foo ...)
(cond
[終了条件 自明の答]
[else (foo 新たなパラメータ)]))
終了条件
再帰呼び出し
Yes
No
自明な解
再帰での終了条件
6
•ある終了条件（例えば、リストが empty に
なるなど）が満足されたら，処理を終える
•リストの rest をとりながら，処理を繰り返
すことが多い
リストでの繰り返しと終了条件
7
パソコン演習
8
•資料を見ながら，「例題」を行ってみる
•各自，「課題」に挑戦する
•自分のペースで先に進んで構いません
パソコン演習の進め方
9
•DrScheme の起動
プログラム → PLT Scheme → DrScheme
•今日の演習では「Intermediate Student」
に設定
Language
→ Choose Language
→ Intermediate Student
→ Execute ボタン
DrScheme の使用
10
•数のリスト a-list から総和を求める関数 list-
sum を作り，実行する
•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
list-sum
(list 1 2 3) 6
入力は
１つのリスト
出力は
１つの数値
入力と出力
15
(define (list-sum a-list)
(cond
[(empty? a-list) 0]
[else (+ (first a-list)
(list-sum (rest a-list)))]))
値を1つ受け取る（入力）
関数の名前
「関数である」ことを
示すキーワード
a-list の値から
リストの総和を求める（出力）
list-sum 関数
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 a-
list)))]))
自明な解
終了条件
リストの総和
19
(empty? a-list)
(+ (first a-list)
(list-sum (rest a-list)))
Yes
No
0 が自明な解である
20
•list-sum の内部に list-sum が登場
•sum の実行が繰り返される
例： (list-sum (list 1 2 3))
= (+ 1 (list-sum (list 2 3)))
(define (list-sum a-list)
(cond
[(empty? a-list) 0]
[else (+ (first a-list)
(list-sum (rest a-list)))]))
リストの総和 list-sum
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))
= ...
= (+ 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
最初の式
実行結果
コンピュータ内部での計算
(list 1 2 3) の和
(list 2 3) の和に1を足す
(list 3) の和に1,2を足す
emptyの和に1,2,3を足す
24
(list-sum (list 1 2 3)) から
(+ 1 (list 2 3)) が得られる過程
= (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
(list-sum (list 1 2 3))
= (cond
[(empty? (list 1 2 3)) 0]
[else (+ (first (list 1 2 3))
(list-sum (rest (list 1 2 3))))])
= (cond
[false 0]
[else (+ (first (list 1 2 3))
(list-sum (rest (list 1 2 3))))])
= (+ (first (list 1 2 3))
(list-sum (rest (list 1 2 3))))
= (+ 1
(list-sum (rest (list 1 2 3))))
= (+ 1
(list-sum (list 2 3)))
この部分は
25
(list-sum (list 1 2 3)) から
(+ 1 (list 2 3)) が得られる過程
= (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
(list-sum (list 1 2 3))
= (cond
[(empty? (list 1 2 3)) 0]
[else (+ (first (list 1 2 3))
(list-sum (rest (list 1 2 3))))])
= (cond
[false 0]
[else (+ (first (list 1 2 3))
(list-sum (rest (list 1 2 3))))])
= (+ (first (list 1 2 3))
(list-sum (rest (list 1 2 3))))
= (+ 1
(list-sum (rest (list 1 2 3))))
= (+ 1
(list-sum (list 2 3)))
この部分は
これは，
(define (sum a-list)
(cond
[(empty? a-list) 0]
[else (+ (first a-list)
(sum (rest a-list)))]))
のa-list を(list 1 2 3) で置き換えたもの
26
(contains-5? (list 3 5 7 9)) から
(contains-5? (list 5 7 9))が得られる過程
(contains-5? (list 3 5 7 9))
= …
=(contains-5? (list 5 7 9))
= …
= true
(contains-5? (list 3 5 7 9))
= (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)))])])
= (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))
この部分は
これは，
(define (contains-5? a-list)
(cond
[(empty? a-list) false]
[else (cond
[(= (first a-list) 5) true]
[else (contains-5? (rest a-list))])]))
のa-list を(list 3 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
average
(list 40 90 80) 70
入力 出力
入力はリスト 出力は数値
入力と出力
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 を使用
list-sum, average の関係
35
•関数 average （例題３）について，実行結果
に至る過程を見る
•(average (list 40 90 80)) から 70 に至る過程を見
る
•DrScheme のstepper を使用する
36
例題４．ステップ実行
(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
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)))
= ...
= (/ 210 3)
= 70
これは，
(define (average a-list)
(/ (list-sum a-list) (lengtha-list)))
のa-list を(list 40 90 80) で置き換えたもの
39
•リストの要素の中に「5」を含むかどうか調
べる関数 contains-5? を作り，実行する
例題５．「5」を含むか調べる
40
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))
「例題５．「5」を含むか調べる」の手順
41
まず，Scheme のプログラムを
コンピュータに読み込ませている
42
これは，
(contains-5? (list 3 5 7 9))
と書いて，a-list の値を
(list 3 5 7 9) に設定しての実行
実行結果である「true」が
表示される
43
contains-5?
(list 3 5 7 9) true
入力は
１つのリスト
出力は
true/false 値
入力と出力
44
;; 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? 関数
45
1. リストが空ならば：→終了条件
false →自明な解
2. そうで無ければ：
•リストの first が「5」であるかを調べ
る．
•「5」ならば： true
•「5」で無いならば: リストの rest が「5」
を含むかどうかを調べる
「5」を含むか調べる
46
．．．
first rest
リストが空で無いとき
．．．
．．． ．．．
「5」で無いならば
「5」 を含むか調べる
「5」 を含むか調べる
「5」を含むか調べる
47
;; 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))])]))
自明な解
終了
条件
「5」を含むか調べる
48
(empty? a-list)
(cond
[(= (first a-list) 5) true]
[else (contains-5? (rest a-list))]
Yes
No
false が自明な解である
49
•contains-5? の内部に contains-5? が登場
•contains-5? の実行が繰り返される
例： (contains-5? (list 3 5 7 9))
= (contains-5? (list 5 7 9))
(define (contains-5? a-list)
(cond
[(empty? a-list) false]
[else (cond
[(= (first a-list) 5) true]
[else (contains-5? (rest a-list))])]))
「5」を含むか調べる contains-5?
50
•関数 contains-5? （例題５）について，実行
結果に至る過程を見る
•(contains-5? (list 3 5 7 9)) から true に至る過程
を見る
•DrScheme のstepper を使用する
51
例題６．ステップ実行
(contains-5? (list 3 5 7 9))
= …
=(contains-5? (list 5 7 9))
= …
= true
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))
= …
=(contains-5? (list 5 7 9))
= …
= true
最初の式
実行結果
コンピュータ内部での計算
(list 3 5 7 9) から探す
(list 5 7 9) から探す
先頭が 5 なので
true
53
(contains-5? (list 3 5 7 9)) から
(contains-5? (list 5 7 9))が得られる過程
(contains-5? (list 3 5 7 9))
= …
=(contains-5? (list 5 7 9))
= …
= true
(contains-5? (list 3 5 7 9))
= (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)))])])
= (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))が得られる過程
(contains-5? (list 3 5 7 9))
= …
=(contains-5? (list 5 7 9))
= …
= true
(contains-5? (list 3 5 7 9))
= (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)))])])
= (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))
この部分は
これは，
(define (contains-5? a-list)
(cond
[(empty? a-list) false]
[else (cond
[(= (first a-list) 5) true]
[else (contains-5? (rest a-list))])]))
のa-list を(list 3 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
product
(list 1 2 3) 32
入力 出力
(list 4 5 6)
入力は，
２つのリスト 出力は数値
入力と出力
60
;; 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)))]))
product 関数
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
(empty? x)
(+ (* (first x) (first y))
(product (rest x) (rest y)))
Yes
No
0 が自明な解である
65
•product の内部に product が登場
•product の実行が繰り返される
例： (product (list 1 2 3) (list 4 5 6))
= (+ (* 1 4) (product (list 2 3) (list 5 6)))
(define (product x y)
(cond
[(empty? x) 0]
[else (+ (* (first x) (first y))
(product (rest x) (rest y)))]))
ベクトルの内積 product
66
•関数 product （例題７）について，実行結果に至
る過程を見る
•(product (list 1 2 3) (list 4 5 6)) から 32 に至る過程を見
る
•DrScheme のstepper を使用する
67
例題８．ステップ実行
(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
基本的な計算式
への展開
演算の実行
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))
= …
= (+ 4
(product (list 2 3) (list 5 6)))
= …
= (+ 4
(+ 10
(product (list 3) (list 6))))
= …
= (+ 4 (+ 10 (+ 18 (product empty empty))))
= …
= 32
(product (list 1 2 3) (list 4 5 6))
= (cond
[(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
[false 0]
[else (+ (* (first (list 1 2 3)) (first (list 4 5 6)))
(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)))
(product (rest (list 1 2 3)) (rest (list 4 5 6))))
= (+ (* 1 4)
(product (rest (list 1 2 3)) (rest (list 4 5 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)))
この部分は
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))
= …
= (+ 4
(product (list 2 3) (list 5 6)))
= …
= (+ 4
(+ 10
(product (list 3) (list 6))))
= …
= (+ 4 (+ 10 (+ 18 (product empty empty))))
= …
= 32
(product (list 1 2 3) (list 4 5 6))
= (cond
[(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
[false 0]
[else (+ (* (first (list 1 2 3)) (first (list 4 5 6)))
(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)))
(product (rest (list 1 2 3)) (rest (list 4 5 6))))
= (+ (* 1 4)
(product (rest (list 1 2 3)) (rest (list 4 5 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)))
この部分は
これは，
(define (product x y)
(cond
[(empty? x) 0]
[else (+ (* (first x) (first y))
(product (rest x) (rest y)))]))
のxを(list 1 2 3) で，yを(list 4 5 6) で置き換えたもの
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 ボタンを押す
⇒すると，実行用ウインドウに（赤い文字で）エラーメッ
セージが表示される（これは実行エラー）
2. DrScheme でstepper を使ってステップ実行を行って，
エラーの箇所を特定しなさい．エラーの原因について
報告しなさい．
(define (list-length a-list)
(cond
[(empty? a-list) 0]
[else (+ 1
(list-length (rest a-list)))]))
(list-length 100)
課題２
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
f(x) = a0+ a1・x + a2・x + ・・・ +an・x
= a0+ ( a1+ ( a2+ ・・・ + ( an-1 + an ・x ) x ・・・) x ) x
例えば， 5 + 6x + 3x
= 5 + ( 6 + 3x ) x
計算手順
①an
②an-1 + an・x
③an-2 + ( an-1 + an・x ) x
・・・ （a0まで続ける）
2n
2
Horner法による多項式の計算
80
さらに勉強したい人への
補足説明資料
81
•(length list)
リストの要素の個数
•(list-ref list n)
リストのｎ番目の要素（先頭は０番目）
これらの関数と同じ機能を持つ関数
my-length, my-list-ref を敢えて書いて
みた例を以下に紹介する
リストに関係する関数
82
•リストの n 番目の要素（先頭は 0 番
目）を得る関数 my-list-ref を作り，
実行する
例題９．リストの n 番目の要素
83
まず，Scheme のプログラムを
コンピュータに読み込ませている
84
これは，
(my-list-ref (list 11 12 13 14) 1)
と書いて，a-list の値を
(list 11 12 13 14) に, nの値を 1
に設定しての実行
実行結果である「12」が
表示される
85
my-list-ref
(list 11 12 13 14) 1
12
入力 出力
入力と出力
86
(define (my-list-ref a-list n)
(cond
[(= n 0) (first a-list)]
[else (my-list-ref (rest a-list) (- n1))]))
値を2つ受け取る（入力）
関数の名前
「関数である」ことを
示すキーワード
a-list とn の値から
n 番目の要素を求める（出力）
my-list-ref 関数
87
(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))
= 12
(my-list-ref (list 11 12 13 14) 1) から12が得られる過程
最初の式
コンピュータ内部での計算
実行結果 88
(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))
= 12
(my-list-ref (list 11 12 13 14) 1) から12が得られる過程
これは，
(define (my-list-ref a-list n)
(cond
[(= n 0) (first a-list)]
[else (my-list-ref (rest a-list) (- n1))]))
のa-list を(list 11 12 13 14) で，nを1で置き換えたも
の
89
(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
1. n = 0 ならば：→終了条件
リストの first →自明な解
2. そうで無ければ：
–「リストの rest を求める（これもリ
スト）．その n-1 番目の要素」が求
める解
リストの n 番目の要素
100
．．．
first rest
n > 0 のとき
．．．
n 番目を探す
．．． ．．．
n-1 番目を探す
リストの n 番目の要素
101
102
リストの n 番目の要素
(define (my-list-ref a-list n)
(cond
[(= n 0) (first a-list)]
[else (my-list-ref (rest a-list) (- n1))]))
自明な解
終了
条件
(= n 0)
(my-list-ref (rest a-list) (- n1))
Yes
No
(first a-list) が自明な解である
103
•my-list-ref の内部に my-list-ref が登場
•my-list-ref の実行が繰り返される
例： (my-list-ref (list 11 12 13 14) 1)
= (my-list-ref (list 12 13 14) 0)
(define (my-list-ref a-list n)
(cond
[(= n 0) (first a-list)]
[else (my-list-ref (rest a-list) (- n1))]))
リストの n 番目の要素 my-list-ref
104
•リストの要素の個数を求める関数
my-length を作り，実行する
例題１０．リストの長さ
105
まず，Scheme のプログラムを
コンピュータに読み込ませている
106
これは，
(my-length (list 11 12))
と書いて，a-list の値を
(list 11 12) に設定しての実行
実行結果である「2」が
表示される
107
my-length
(list 11 12) 2
入力 出力
入力と出力
108
(define (my-length a-list)
(cond
[(empty? a-list) 0]
[else (+ 1
(my-length (rest a-list)))]))
値を1つ受け取る（入力）
関数の名前
「関数である」ことを
示すキーワード
a-list の値から
リストの長さを求める（出力）
my-length 関数
109
(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))))]))
(my-list-ref (list 11 12)) から 2 が得られる過程 (1/2)
最初の式
コンピュータ内部での計算 110
= (+ 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
(my-list-ref (list 11 12)) から 2 が得られる過程 (2/2)
コンピュータ内部での計算
実行結果
111
(my-length (list 11 12)) から
2 が得られる過程の概略
(list 11 12) の長さ
(list 12) の長さに１を足す
empty の長さに２を足す
(my-length (list 11 12))
= ...
= (+ 1 (my-length (list 12)))
= ...
= (+ 1 (+ 1 (my-length 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
117
リストの長さ
(define (my-length a-list)
(cond
[(empty? a-list) 0]
[else (+ 1
(my-length (rest a-list)))]))
自明な解
終了条件
(empty? a-list)
(+ 1
(my-length (rest a-list)))
Yes
No
0 が自明な解である
118
•my-length の内部に my-length が登場
•my-length の実行が繰り返される
例： (my-length (list 11 12))
= = (+ 1 (my-length (list 12)))
(define (my-length a-list)
(cond
[(empty? a-list) 0]
[else (+ 1
(my-length (rest a-list)))]))
リストの長さ my-length
119
