リストとは• 不定数のデータの並び(合成データ)• データの並びには順序があり操作は先頭側から情報処理演習II要素を加えだんだん長く

第6回
任意長の合成データ：リスト

23, 32, 6, 8 の順に，リストに加える例

終端

最初は空2323を加える
32を加える

3223

632

23

63223

同様に続く…
先頭側：後から加えた側。操作はこちらから

8

終端側：先に加えた要素はこちら側

リスト
 要素の列挙での記述(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 が空リストか判断

例題１. リストの n 番目の要素


リストの n 番目の要素（先頭は 1 番目）を得る関数 my-list-ref を定義し，実行する。

入力は１つのリストと１つの数値

出力は指定
番目の要素

my-list-ref(list 11 12 13 14)
212

リスト処理の再帰関数のテンプレート
リスト処理関数一般のテンプレート(define (fun_for_list a-list)(cond[(empty? a-list) …][else … (first a-list) …
… (fun_for_list (rest a-list)) …]))

今回の関数 my-list-ref のテンプレート(define (my-list-ref a-list n)(cond[(= n 1) …][else … (my-list-ref (rest a-list)(- n 1)) …]))

1例題1.リストの n 番目の要素
1. n = 1 ならば：(終了条件)
解は (first a-list) (自明な解)
2. そうでなければ：– 「リストの rest 部」の「n–1 番目の要素」が求める解

例題1.リストの n 番目の要素;; my-list-ref: list number -> anything;; get the n-th element of a list;; (my-list-ref (list 11 12 13 14) 2) = 12
(define (my-list-ref a-list n)(cond 終了条件 自明な解[(= n 1) (first a-list)][else (my-list-ref (rest a-list)(- n 1))]))

No(= n 1)
Yes(my-list-ref (rest a-list) (- n 1))(first a-list) が自明な解

例題１の実行例(1/2)

my-list-ref の内部に my-list-ref (再帰による繰り返し)
例： (my-list-ref (list 11 12 13 14) 2)= (my-list-ref (list 12 13 14) 1)

例題１の実行例(2/2)
これは，(my-list-ref (list 11 12 13 14) 2)と書いて，a-list の値を(list 11 12 13 14) に，n の値を 2 に設定して実行

まず，Scheme のプログラムをコンピュータに読み込ませている
実行結果である「12」が表示される(my-list-ref (list 11 12 13 14) 2) から12が得られる過程(my-list-ref (list 11 12 13 14) 2) から12が得られる過程(my-list-ref (list 11 12 13 14) 2) 最初の式
= (cond[(= 2 1) (first (list 11 12 13 14))][else (my-list-ref (rest (list 11 12 13 14) ) (- 2 1))])= (cond[false (first (list 11 12 13 14))][else (my-list-ref (rest (list 11 12 13 14) ) (- 2 1))])= (my-list-ref (rest (list 11 12 13 14) ) (- 2 1))= (my-list-ref (list 12 13 14) (- 2 1))= (my-list-ref (list 12 13 14) 1)= (cond[(= 1 1) (first (list 12 13 14))][else (my-list-ref (rest (list 12 13 14) ) (- 1 1))])= (cond[true (first (list 12 13 14))][else (my-list-ref (rest (list 12 13 14) ) (- 1 1))])
コンピュータ内部での計算= (first (list 12 13 14))
= 12 実行結果(my-list-ref (list 11 12 13 14) 2)= (cond[(= 2 1) (first (list 11 12 13 14))][else (my-list-ref (rest (list 11 12 13 14) ) (- 2 1))])= (cond[false (first (list 11 12 13 14))][else (my-list-ref (rest (list 11 12 13 14) ) (- 2 1))])=これは，(my-list-ref (rest (list 11 12 13 14) ) (- 2 1))= (my-list-ref(list 12 13 14)a-list(- 2 1))(define (my-list-refn)= (my-list-ref(cond (list 12 13 14) 1)= (cond [(= n 1) (first a-list)][(= 1[else1) (first(list 12 13 (rest14))] a-list) (- n 1))]))(my-list-ref[else (my-list-ref (rest (list 12 13 14) ) (- 1 1))])のa-listを(list111213 14) で，n を 2 で置
= (cond[true (first (list 12 13 14))]
き換えたもの。
[else (my-list-ref (rest (list 12 13 14) ) (- 1 1))])= (first (list 12 13 14))= 122

(my-list-ref (list 11 12 13 14) 2) から12が得られる過程の概略

my-list-ref関数のステップ実行(1/10)(my-list-ref (list 11 12 13 14) 2) リストの2番目の要素=…
= (my-list-ref (list 12 13 14) 1)= …
= (first (list 12 13 14))

リストの rest を取って，その1番目の要素= 12

リストの先頭my-list-ref の「a-list」は「(list 11 12 13 14)」で，「n」は「2」で置き換わる。

my-list-ref関数のステップ実行(2/10)

my-list-ref関数のステップ実行(3/10)「(= 2 1)」 は「false」で置き換わる。

「(cond [false 式Ｘ] [else 式Ｙ])」は「else 式Ｙ」節が残る。

my-list-ref関数のステップ実行(4/10)

my-list-ref関数のステップ実行(5/10)「(cond [else 式Ｙ])」は「式Ｙ」で置き換わる。

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

3my-list-ref関数のステップ実行(6/10)

my-list-ref関数のステップ実行(7/10)「(- 2 1)」は「1」で置き換わる。

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

my-list-ref関数のステップ実行(8/10)

my-list-ref関数のステップ実行(9/10)「(= 1 1)」 は「true」で置き換わる。

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

my-list-ref関数のステップ実行(10/10)

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

4

DrScheme の使用

実習の進め方 資料を見ながら，「実習」を行ってみる

 DrScheme の起動

プログラム → PLT Scheme → DrScheme その後，各自「課題」に挑戦する– 各自で自習 ＋ 巡回指導
– 遠慮なく質問してください 今日の実習では「Intermediate Student」に設定
Language 自分のペースで先に進んで構いません→ Choose Language→ Intermediate Student→ OK ボタン

DrScheme の使用 / ステップ実行

実習１. リスト

 プログラム実行の振る舞いを観察するツール 「定義用ウインドウ」のみを使用「list」 を使ってリストを書く（通常の実行と異なる）
 「Intermediate Student」に設定する必要あり

１５８６３２２３Language → Choose Language→ Intermediate Student

手順：次の式を「実行用ウインドウ」で実行→ Run ボタン

(list 15 8 6 32 23)「実習1．リスト」の手順

1. 次を「実行用ウインドウ」で実行しなさい(list 15 8 6 32 23)

実行結果の例「(list 15 8 6 32 23)」を入力すると「(list 15 8 6 32 23)」と表示される

5

実習２．リストの first と rest

コンピュータが行っていること
Scheme の式(list 15 8 6 32 23)を入力すると・・・

 リスト (listて，first と rest を実行する
rest

first１５

インタプリタDrScheme

15 8 6 32 23) に対し

８６３２２３

手順：次の式を「実行用ウインドウ」で実行(list 15 8 6 32 23)

式の実行結果がそのまま表示される「実習２．リストの first と rest」の手順(first (list 15 8 6 32 23))
(rest (list 15 8 6 32 23))

実行結果の例

1. 次を「実行用ウインドウ」で実行しなさい
first の実行結果(first (list 15 8 6 32 23))
(rest (list 15 8 6 32 23))

restの実行結果

関数 first
Scheme の式

関数 rest(first (list 15 8 6 32 23))

Scheme の式(rest (list 15 8 6 32 23))を入力すると・・・を入力すると・・・

インタプリタDrScheme

インタプリタDrScheme(list 8 6 32 23)

15が表示される式の実行結果リストの先頭の要素

式の実行結果が表示されるリストから先頭の要素を除いた残り（長さは１短い）

6

実習３. リストの first と rest 要素が１つしか無いリスト (list15)に対して，first と rest を実行する
first「実習３．リストの first と rest」の手順

1. 次を「実行用ウインドウ」で実行しなさい

rest

１５

(first (list 15))
(rest (list 15))

empty

手順：次の式を「実行用ウインドウ」で実行(first (list 15))
(rest (list 15))

実習４. リストの基本操作

実行結果の例

リストの第三要素を得る関数 element3 を定義し，実行する

first の実行結果

例）

１５８６３２２３

３番目

restの実行結果入力

element3(list 15 8 6 32 23)

rest関数とfirst関数による第三要素の抽出
first と rest を使い第三要素を求める関数＝ リストの rest の rest の first

１５８rest６first
rest

３２２３

出力
6

第三要素を求める element3 関数「関数である」ことを示すキーワード

値を１つ受け取る（入力）関数の名前(define (element3 a-list)(first (rest (rest a-list))))a-list の値から３番目の要素を求める（出力）7実習４の実行例(1/2)

「実習４．リストの基本操作」の手順
1. 次を「定義用ウインドウ」で，実行しなさい•

入力した後に，Run ボタンを押す;; element3: list of anything -> anything;; Get the 3rd element of a list;; (list-sum (list 15 8 6 32 23)) = 6(define (element3 a-list)

まず，Scheme のプログラムをコンピュータに読み込ませている(first (rest (rest a-list))))2. その後，次を「実行用ウインドウ」で実行しなさい(element3 (list 1 2 3 4))(element3 (list 15 8 6 32 23))(element3 (list 15 8 6 32 23)) から6が得られる過程

実習４の実行例(2/2)
これは，(element3 (list 15 8 6 32 23))と書いて，a-list の値を(list 15 8 6 32 23) に設定しての実行(element3 (list 15 8 6 32 23)) 最初の式
= (first (rest (rest (list 15 8 6 32 23))))= (first (rest (list 8 6 32 23)))= (first (list 6 32 23))
= 6

コンピュータ内部での計算

実行結果実行結果である「6」が表示される(element3 (list 15 8 6 32 23)) から6が得られる過程

実習４の関数 element3 について
 リストの長さが２以下の時には，「エラーメッ(element3 (list 15 8 6 32 23))
= (first (rest (rest (list 15 8 6 32 23))))= (first (rest (list 8 6 32 23)))

セージ」が表示される
例）(element3 (list 1 2))→ エラーメッセージが表示される

これは，= (first(list 6 32 23))
= 6

(define (element3 a-list)(first (rest (rest a-list))))の a-list を (list 15 8 6 32 23) で置き換えたもの。

8element3関数で起こるエラーの例
これは，(element3 (list 1 2))と書いて，a-list の値を(list 1 2) に設定して実行(element3 (list 1 2)) から実行エラーに至る過程(element3 (list 1 2)) 最初の式

(first (rest(rest a-list)))に a-list = (list 1 2)が代入される= (first (rest (rest (list 1 2)))
(rest (list 1 2)) → (list 2)= (first (rest (list 2)))
(rest (list 1)) → empty= (first empty)

エラーメッセージが表示される

コンピュータ内部での計算→ 「空リスト empty に対して first を実行できない」という決まりがあるので，実行エラーになる。

実習５. 全ての要素が１０以上か？

リスト処理の再帰関数のテンプレート

数値リスト a-list の要素を調べ，全ての要素が１０以上のとき（＝１０未満の要素が無いとき）にのみ true を返す関数 all-are-largeを定義し，実行する

リスト処理関数一般のテンプレート(define (fun_for_list a-list)(cond[(empty? a-list) …][else … (first a-list) …
… (fun_for_list (rest a-list)) …]))

入力

出力

all-are-large

数値のリスト例：(list 10 11 12)

ブール値
例：true

実習５．全ての要素が１０以上か？
;; all-are-large: list number -> boolean;; If some elements are "<10",;; it returns false;; (all-are-large (list 10 11 12) = true
(define (all-are-large alon)
(cond
終了条件
自明な解
[(empty? alon) true][else (and (<= 10 (first alon))(all-are-large (rest alon)))]))
all-are-large の内部に all-are-large(再帰による繰り返し)
例： (all-are-large (list 10 11 12))= (all-are-large (list 11 12))

今回の関数 all-are-large のテンプレート(define (all-are-large alon)(cond[(empty? alon) …][else … (first alon) …
… (all-are-large (rest alon)) …]))

「数値リストの要素の和の手順
1. 次を「定義用ウインドウ」で，実行しなさい•

入力した後に，Run ボタンを押す;; all-are-large: list number -> boolean;; If some elements are "<10", it returns false;; (all-are-large (list 10 11 12) = true
(define (all-are-large alon)(cond[(empty? alon) true][else (and (<= 10 (first alon))(all-are-large (rest alon)))]))

2. その後，次を「実行用ウインドウ」で実行しなさい(all-are-large (list 10 11 12))(all-are-large (list 7 8 9))9

実習６. 構造体のリスト
AddressNote 構造体のリストから，年齢が全て１２歳以下であるかを調べる関数 all_are_child を作る– 12 歳以上の人がいなければ true

リスト処理の再帰関数のテンプレート
AddressNote

nameageaddress– 構造体1つで1人分 → 構造体のリス
トで複数人分
入力は AddressNote
構造体のリスト

all_are_child(list(make-AddressNote "Ken" 11 "Fukuoka")(make-AddressNote "Bill" 30 "Saga")(make-AddressNote "Mike" 8 "Nagasaki"))

出力はbooleanfalse

リスト処理関数一般のテンプレート(define (fun_for_list a_list)(cond[(empty? a_list) …][else … (first a_list) …
… (fun_for_list (rest a_list)) …]))
先頭要素が構造体
今回の関数 all_are_child のテンプレート
データなのでさらに(define (all_are_child a_list)
セレクタ を使いフィー(condルドデータを参照[(empty? a_list) …][else … (AddressNote-age (first a_list))… (all_are_child (rest a_list)) …]))

実習６. 構造体のリスト「実習６. 構造体のリスト」の手順
1. 次を「定義用ウインドウ」で，実行しなさい(define-struct AddressNote
構造体定義(name age address));; all_are_child:;;a list of AddressNote ->boolean;; If some AddressNotes whose age is more;; than 12, it returns false(define (all_are_child a_list)(cond終了条件
自明な解[(empty? a_list) true][else (and(> 12 (AddressNote-age (first a_list)))(all_are_child (rest a_list)))]))•

入力した後に，Run ボタンを押す(define-struct AddressNote(name age address));; all_are_child:;;a list of AddressNote ->boolean;; If some AddressNotes whose age is more;; than 12, it returns false(define (all_are_child a_list)(cond[(empty? a_list) true][else (and (> 12 (AddressNote-age (first a_list)))(all_are_child (rest a_list)))]))

2. その後，次を「実行用ウインドウ」で実行しなさい(all_are_child (list(make-AddressNote "Ken" 11 "Fukuoka")(make-AddressNote "Bill" 30 "Saga")(make-AddressNote "Mike" 8 "Nagasaki")))課題１
関数first，rest についての問題– 次の式の実行結果はどうなるか。解答せよ。

課題

1. (rest(list 1 2 3))(rest (list 1 2 3)))3. (rest (rest (list 1 2 3)))4. (first (rest (rest (list 1 2 3))))5. (rest (rest (rest (list 1 2 3))))
2. (first10

課題２

課題３

以下の組み合わせのリスト演算を実行するとどうなるか–「エラー」の場合には，「エラー」と記入すること–DrScheme では「実行用ウインドウ」を使い確認
リストが(list 1) の場合リストが(list 1 2) の場合

 関数 list-sum についての問題– (list-sum (list 1 2 3)) から 6 が得られる過程の概略を数行程度で説明しなさい– DrScheme のステップ実行機能を使いなさい

リストが(list 1 2 3) の場合(first リスト) の実
行結果(define (list-sum a-list)(cond[(empty? a-list) 0][else (+ (first a-list)(list-sum (rest a-list)))]))(rest リスト) の実
行結果(first (rest リスト))の実行結果(first (rest (rest リスト))) の実行結果

課題４
 DrScheme のステップ実行機能を利用した実行エ

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

課題５
 リストの要素の中に 「偶数」を含むかどうか調べる関数 all_are_even を定義し，実行結果を報告しなさい– 偶数を１つでも含めば true
– 偶数を１つも含まなければ false– 例えば，(all_are_even (list 1 3 4)) = true
(all_are_evne empty) = false– 関数 even? を使うこと

課題６
 AddressNote 構造体のリストから，年齢(age)の平均を求める関数 average-age を定義し，実行結果を報告しなさい

課題７
 n次の多項式f(x) = a0 + a1・x + a2・x2 + ・・・ +an・xnについて，次数 n と，係数 a0 ・・・ an から，f(x)を計算するプログラムを定義しなさい– 次ページ以降で説明する Horner 法を使うこと– 次数 n は入力として与えなくても実現できる

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

Horner法による多項式の計算
f(x) = a0 + a1・x + a2・x2 + ・・・ +an・xn= a0 + (a1 + (a2 +・・・+ (an-1 + an ・x ) x ・・・) x ) x
例えば，

5 + 6x + 3x2= 5 + ( 6 + 3x ) x

計算手順
① an
② an-1 + an・x
③ an-2 + ( an-1 + an・x ) x・・・ （a0 まで続ける）

12