Document

6. リスト処理関数の設計(発展版)
プログラミング論 I
例題1. ベクトルの内積
同じ長さのリストとして表現された2つのベクトル
データ x, y の内積を求める関数 product を作る
※ただし，ベクトルx, yの要素数（長さ）は等しいとする．
product
入力は，
2つのリスト
(list 1 2 3)
(list 4 5 6)
出力は数値
32
リスト処理の再帰関数のテンプレート
リスト処理関数一般のテンプレート
(define (fun_for_list a_list)
(cond
[(empty? a_list) …]
[else … (first a_list) …
… (fun_for_list (rest a_list)) …]))
今回の関数 product のテンプレート
今回は2つのリスト
(ベクトル)を処理
する必要がある
(define (product x y)
(cond
[(empty? x) …]
[else … (first x) … (first y) …
… (product (rest x) (rest y)) …]))
例題1.ベクトルの内積
1. リストが空ならば： (終了条件)
解は 0
(自明な解)
2. そうでなければ：
– 「 2つのリストの先頭の積」と、「2つのリス
トの rest 部の内積」の「和」が求める解
(empty? x)
Yes
0 が自明な解
No
(+ (* (first x) (first y))
(product (rest x)(rest y)))
例題1.ベクトルの内積
;; product: list list -> number
;; inner product of two vectors
;; (product (list 1 2 3) (list 4 5 6)) = 32
(define (product x y)
今回は2つのリスト
(cond 終了条件自明な解
(ベクトル)を処理
[(empty? x) 0]
する必要がある
[else (+ (* (first x) (first y))
first部の処理
(product (rest x) (rest y)))]))
結果とrest部の
処理結果を足す
product の内部に product (再帰による繰り返し)
例： (product (list 1 2 3) (list 4 5 6))
= (+ (* 1 4)(product (list 2 3)(list 5 6)))
練習1.ベクトルの内積
(product (list 1 2 3 4) (list 5 6 7 8)) の
計算過程の概要と結果を示せ。
例題2. 構造体のリスト
リストの要素は単純値以外でもよい → 構造体やリストも可
AddressNote 構造体のリストから名前(name) AddressNote
のリストを得る関数 select_name を作る
name
–（参考： AddressNote は第4回目の資料の
personal_info と同様の構造体)
age
address
–構造体1つで1人分 → 構造体のリストで複数人分
入力は AddressNote
構造体のリスト
Select_name
(list
(make-AddressNote "Ken" 35 "Fukuoka")
(make-AddressNote "Bill" 30 "Saga")
(make-AddressNote "Mike" 28 "Nagasaki"))
出力は文字列
(name)のリスト
(list
"Ken" "Bill" "Mike")
リスト処理の再帰関数のテンプレート
リスト処理関数一般のテンプレート
(define (fun_for_list a_list)
(cond
[(empty? a_list) …]
[else … (first a_list) …
… (fun_for_list (rest a_list)) …]))
今回の関数 select_name のテンプレート
(define (select_name a_list) 先頭要素が構造体データ
なのでさらにセレクタを使
(cond
いフィールドデータを参照
[(empty? a_list) …]
[else … (AddressNote-name (first a_list))
… (select_name (rest a_list)) …]))
例題2. 構造体のリスト
(define-struct AddressNote
構造体定義
(name age address))
;; select_name:
;;
a list of AddressNote -> a list of string
;; to select name from an AddressNote list
(define (select_name a_list)
要素が構造体のリストなの
(cond
終了条件
自明な解
でさらにセレクタを適用し
[(empty? a_list) empty]
フィールドデータを参照
[else (cons
(AddressNote-name (first a_list))
first部の処理結果 (select_name (rest a_list)))]))
とrest部の処理結果
リストをconsで結合し
て結果リストを作る
C言語
練習2. 構造体のリスト
AddressNote 構造体のリストから年齢(age)
のリストを得る関数 select_age を作る
入力は AddressNote
構造体のリスト
select_age
(list
(make-AddressNote "Ken" 35 "Fukuoka")
(make-AddressNote "Bill" 30 "Saga")
(make-AddressNote "Mike" 28 "Nagasaki"))
AddressNote
name
age
address
出力は数(age)
のリスト
(list 35 30 28)
次に AddressNote 構造体のリストから，年齢(age)の
平均を求める関数 average_age を作る
例題3. 自然数処理
n から 1 までの自然数を要素に持つリスト
を生成する関数 naturals を作る
naturals
入力は
1つの自然数
3
出力は自然数
のリスト1つ
(list 3 2 1)
自然数を定義する(再帰的データ)
任意数の要素を持つリストを再帰により定式化した
→ 同様に自然数も定式化してみる
(自然数もその要素が任意の大きさであるデータの一つ)
列挙記述 0, 1, 2, … から非形式的 “...” を取るため自己参照で記述
0 は自然数である。
もし n が自然数なら、n より1だけ大きいものも、そうである。
↓ Scheme-style のデータ記述
自然数とはいずれかである
1. 0 または
2. (add1 n)、もし n も自然数なら。
ここで演算 add1 は自然数に 1 を加えるもの。
(リスト同様、上記の 2 は自己参照を持つが、1は持たない)
自然数を定義する(再帰的データ)
データ定義から例を組み立てる
0
は最初の自然数。
(add1 0)
は次の自然数。
(add1 (add1 0)) はその次の自然数。以下同様…
これは、リスト構築プロセスと類似：
• empty から始め cons で要素を加えることでリストを作った。
⇒ 今度は 0 から始めて 1 を add することで自然数を作る。
(自然数は省略記法を持つ：(add1 0) は 1、(add1 (add1 0)) は 2、など)
リスト処理では cons されたリストを抽出するのに rest を使った
(rest (cons a_value a_list)) = a_list
自然数でこの “extraction” を行う演算は sub1 (次の法則を満足)
(sub1 (add1 n)) = n
再帰関数のテンプレート
リストを処理する関数のテンプレート
(define (fun_for_list a_list)
(cond
[(empty? a_list) …]
[else … (first a_list) …
… (fun_for_list (rest a_list)) …]))
自然数を処理する関数のテンプレート
(define (fun-for-natural n)
リスト処理の empty? に相当。意味は (= n 0) と同じ
(cond
[(zero? n) …]
[else … n … (fun-for-natural (sub1 n)) …]))
リスト処理の rest に相当。意味は (- n 1) と同じ
例題3. 自然数処理
1. n が 0 ならば(終了条件) ：empty (自明な解)
2. そうでなければ：
– (sub1 n) に対する結果の先頭に n を加える
– リストの先頭に n をつなげるために cons を使う
;;naturals: number -> list-of-numbers
;; to create a list of numbers (n to 1)
;; (naturals 3) = (list 3 2 1)
(define (naturals n)
(cond
[(zero? n) empty]
[else (cons n (naturals (sub1 n)))]))
naturals の中に naturals (再帰で繰り返し)
例：(naturals 3) = (cons 3 (naturals 2))
(naturals 3) から
(list 3 2 1) が得られる過程の概略
(naturals
= …
= (cons 3
= …
= (cons 3
= …
= (cons 3
= …
= (cons 3
= (list 3
3)
最初の式
(naturals 2))
(cons 2 (naturals 1)))
(cons 2 (cons 1 (naturals 0))))
(cons 2 (cons 1 empty)))
コンピュータ内部での計算
2 1)
実行結果
練習3. 自然数処理
1から n までの自然数を要素に持つリスト
を生成する関数 naturals2 を作る
naturals2
入力は
1つの自然数
3
出力は自然数
のリスト1つ
(list 1 2 3)
ヒント
自然な考え方
• 2つの引数を取る補助関数naturals2-subを定
義する．
;; naturals2-sub : number number -> (listof
number)
;; to produce a list of natural numbers, whose
elements start i to n. When i becomes greater
than n, return the list produced.
(define (naturals2-sub i n) ... )
少々難問！
別の観点から
• ある数をリストの末尾に置くmake-last-itemを
補助関数として定義し，これを利用する．
;;make-last-item : num (listof num)->(listof num)
;;(make-last-item 3 (list 1 2)) should produce (list 1 2 3)
n=3の時，(- n 1)は
2なので，(list 1 2)
;;(naturals2 n)
;; もし n=1 ならば (list n)
;; そうでなければ，nを，(naturals2 (- n 1))で作るリスト
の最後に置く．
例題4. 要素の挿入
• ソート(整列)されたリストに，整列関係を保って
要素を挿入する関数 insert を作る
– この例では要素が大きい順に整列されているとする
insert
入力は，数と
整列済みのリスト
出力は要素挿入
後の整列済リスト
(list 80 40 21 10 7 5 4)
40
(list 80 21 10 7 5 4)
例題4. 要素の挿入
リスト処理のテンプレートをもとに具体化
1. リストが空ならば(終了条件) ：
(cons n empty)
; 要素が1つのリスト
2. そうでない場合：整列関係を保つ位置にnを挿入
– 先頭要素 ≦ n なら→ nが最大なので先頭に挿入
(cons n alon) が整列済みの結果
– 先頭要素＞ n なら→ nの挿入は尾部のどこか
rest部への再帰。その結果と先頭要素を結合
(rest部への再帰的な呼出も意図通りに機能するという前提)
例題4. 要素の挿入
(empty? lon)
Yes
No
(cond [(<= (first lon) n) (cons n lon)]
[(> (first lon) n)
(cons (first lon)
(insert n (rest lon)))])
(<= (first lon) n)
No
Yes
(cons n lon) が解
(cons n empty) が解
再帰 (insert n (rest lon))
でrest部への挿入を試み、その
結果と (first lon)を結合
例題4. 要素の挿入
;;insert: number list-of-numbers->list-of-numbers
;;create a list of numbers from n and numbers on alon that
;; is sorted in descending order; alon is already sorted
;;insert: number list-of-numbers(sorted)
;;
-> list-of-numbers(sorted)
(define (insert n alon)
(cond
[(empty? alon) (cons n empty)]
[else (cond
[(<= (first alon) n) (cons n alon)]
[(> (first alon) n)
(cons (first alon)
(insert n (rest alon)))])]))
insert の定義内に insert の適用(再帰による繰り返し)
例： (insert 40 (list 80 21 10 7 5 4))
= (cons 80 (insert 40 (list 21 10 7 5 4)))
(insert 20 (list 80 21 10 7 5 4)) から
(list 80 21 20 10 7 5 4)) を得る過程の概略
(insert 20 (list 80 21 10 7 5 4))
= …
= (cons 80 (insert 20
(rest (list 80 21 10 7 5 4))))
= (cons 80 (insert 20 (list 21 10 7 5 4)))
= …
= (cons 80 (cons 21
(insert 20 (list 10 7 5 4)))
= …
= (cons 80 (cons 21 (list 20 10 7 5 4)))
= (list 80 21 20 10 7 5 4)
例題5. インサーションソート
例題4の insert を補助関数として使い、リストを
ソートする関数 sort を作る
– ここでは，大きい順にソートする
入力はリスト
出力はソート済みリスト
sort
(list 3 5 1 4)
→ (list 5 4 3 1)
(list 1 3 5 7 10 21 4 80)
→ (list 80 21 10 7 5 4 3 1)
例題5.インサーションソート
ソート済リストに insert を使って要素を挿入したも
のもまたソート済リスト
1.リストが空なら(終了条件) ： empty が解
2.そうでなければ：要素を1つずつ取り出しなが
らその時点での整列済みリストを作る
→ rest部への再帰呼出の結果に (それが意
図通り整列済みリストであるという前提で)
first 要素を補助関数 insert で挿入する
例題5.インサーションソート
;; sort: list-of-numbers -> list-of-numbers
(define (sort lon)
(cond
[(empty? lon) empty]
[else (insert (first lon)(sort (rest lon)))]))
No
(empty? lon)
Yes
empty
(insert (first lon)
(sort (rest lon)))
sort の定義内部に sort の関数適用(再帰的繰り返し)
例：(sort (list 3 5 1 4)) = (insert 3 (sort (list 5 1 4)))
(sort (list 3 5 1 4))
の計算過程の概略
(sort (list 3 5 1 4))
…
= (insert 3 (sort (list 5 1 4)))
…
= (insert 3 (insert 5 (sort (list 1 4))))
…
= (insert 3 (insert 5 (insert 1 (sort (list 4)))))
…
= (insert 3 (insert 5 (insert 1 (insert 4 (sort empty)))))
…
= (insert 3 (insert 5 (insert 1 (insert 4 empty))))
…
= (insert 3 (insert 5 (cons 4 (insert 1 (rest (list 4))))))
= (insert 3 (insert 5 (cons 4 (insert 1 empty))))
…
= (insert 3 (insert 5 (cons 4 (cons 1 empty))))
= …
= (insert 3 (cons 5 (list 4 1)))
= …
= (cons 5 (insert 3 (list 4 1)))
= …
= (cons 5 (cons 4 (insert 3 (list 1)))
= …
= (cons 5 (cons 4 (cons 3 (list 1)))
= (list 5 4 3 1)
練習4. インサーションソート
例題5(および例題4)を参考にリストを、今度は小
さい順に、ソートする関数 sort2 を作る
入力はリスト
出力はソート済みリスト
sort2
(list 3 5 1 4)
→ (list 1 3 4 5)
(list 7 1 80 3 21 5 10 4)
→ (list 1 3 4 5 7 10 21 80)
課題
課題1. 奇数のリスト
•
自然数 n から，「1番目からn番目の奇数のリ
スト」を作る関数 odd_list を作成せよ。
–
例えば (odd-list 4) = (7 5 3 1)
Odd-list
;; odd-list: number -> (listof number)
;; (odd-list 4) -> (list 7 5 3 1)
(define (odd-list n)
(cond
[(= n 0) empty]
[else (cons (- (* 2 n) 1)
(odd-list (- n 1)))]))
課題2. 構造体リスト処理(フィルタリング)
AddressNote 構造体(例題2)についての問題
– 年齢 an_ageとAddressNote 構造体のリスト a_list を
入力とし，年齢が an_age に一致する人のリストを出力
する関数 select_by_age を作成せよ。
例えば
(select-by-age 35
(list (make-address-note
(make-address-note
(make-address-note
= (list (make-address-note
(make-address-note
“Kaneko” 35 “Hakozaki”)
“Tanaka” 34 “Kaizuka”)
“Saito” 35 “Tenjin”)))
“Kaneko” 35 “Hakozaki”)
“Saito” 35 “Tenjin”))
select_by_age
;;(select-by-age 35
;;
(list (make-address-note “Kaneko” 35 “Hakozaki”)
;;
(make-address-note “Tanaka” 34 “Kaizuka”)
;;
(make-address-note “Saito” 35 “Tenjin”)
)
;;= (list (make-address-note “Kaneko” 35 “Hakozaki”)
;;
(make-address-note “Saito” 35 “Tenjin”))
)
;; select_by_age: age (listof address-node) => (listof address_node)
(define (select_by_age aloAN age)
(cond
[(empty? aloAN)
empty]
[(= (address-node-age (first aloAN)) age)
(cons (first aloAN) (select_by_age (rest aloAN) age))]
[else (select_by_age (rest aloAN) age)
] ))

Download Report