6. リスト処理関数の設計(発展版) プログラミング論 I.

Presentation on theme: "6. リスト処理関数の設計(発展版) プログラミング論 I."— Presentation transcript:

1 6. リスト処理関数の設計(発展版) プログラミング論 I

2 例題1. ベクトルの内積 入力は， 2つのリスト 出力は数値
同じ長さのリストとして表現された2つのベクトルデータ x, y の内積を求める関数 product を作る ※ただし，ベクトルx, yの要素数（長さ）は等しいとする． product 入力は， 2つのリスト 出力は数値 (list 1 2 3) (list 4 5 6) 32

3 リスト処理の再帰関数のテンプレート リスト処理関数一般のテンプレート 今回の関数 product のテンプレート
(define (fun_for_list a_list) (cond [(empty? a_list) …] [else … (first a_list) … … (fun_for_list (rest a_list)) …])) 今回の関数 product のテンプレート (define (product x y) [(empty? x) …] [else … (first x) … (first y) … … (product (rest x) (rest y)) …])) 今回は2つのリスト (ベクトル)を処理 する必要がある

4 例題1.ベクトルの内積 リストが空ならば： (終了条件) 解は 0 (自明な解) そうでなければ：
リストが空ならば： (終了条件)　 解は 0 (自明な解) そうでなければ：　 「 2つのリストの先頭の積」と、「2つのリストの rest 部の内積」の「和」 が求める解 No (empty? x) Yes (+ (* (first x) (first y)) (product (rest x)(rest y))) 0 が自明な解

5 例題1.ベクトルの内積 ;; 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つのリスト (ベクトル)を処理 する必要がある 終了条件 自明な解 first部の処理 結果とrest部の 処理結果を足す product の内部に product (再帰による繰り返し) 例： (product (list 1 2 3) (list 4 5 6)) = (+ (* 1 4)(product (list 2 3)(list 5 6)))

6 練習1.ベクトルの内積 (product (list 1 2 3　4) (list ))　の計算過程の概要と結果を示せ。

7 例題2. 構造体のリスト Select_name
リストの要素は単純値以外でもよい → 構造体やリストも可 AddressNote 構造体のリストから名前(name)のリストを得る関数 select_name を作る （参考： AddressNote は第4回目の資料の personal_info と同様の構造体) 構造体1つで1人分 → 構造体のリストで複数人分 AddressNote name age address 入力は AddressNote 構造体のリスト Select_name 出力は文字列 (name)のリスト (list (make-AddressNote "Ken" 35 "Fukuoka") (make-AddressNote "Bill" 30 "Saga") (make-AddressNote "Mike" 28 "Nagasaki")) (list "Ken" "Bill" "Mike")

8 リスト処理の再帰関数のテンプレート リスト処理関数一般のテンプレート 今回の関数 select_name のテンプレート
(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) [else … (AddressNote-name (first a_list)) … (select_name (rest a_list)) …])) 先頭要素が構造体データ なのでさらにセレクタ を使 いフィールドデータを参照

9 例題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)) (select_name (rest a_list)))])) 構造体定義 要素が構造体のリストなの でさらにセレクタを適用し フィールドデータを参照 終了条件 自明な解 first部の処理結果 とrest部の処理結果 リストをconsで結合し て結果リストを作る

10 C言語

11 練習2. 構造体のリスト AddressNote 構造体のリストから年齢(age)のリストを得る関数 select_age を作る AddressNote name age address 入力は AddressNote 構造体のリスト select_age 出力は数(age) のリスト (list (make-AddressNote "Ken" 35 "Fukuoka") (make-AddressNote "Bill" 30 "Saga") (make-AddressNote "Mike" 28 "Nagasaki")) (list ) 次に AddressNote 構造体のリストから，年齢(age)の 平均を求める関数 average_age を作る

12 例題3. 自然数処理 n から 1 までの自然数を要素に持つリストを生成する関数 naturals を作る naturals 3
出力は自然数 のリスト1つ 入力は 1つの自然数 3 (list 3 2 1)

13 自然数を定義する(再帰的データ) 任意数の要素を持つリストを再帰により定式化した → 同様に自然数も定式化してみる
(自然数もその要素が任意の大きさであるデータの一つ) 列挙記述 0, 1, 2, … から非形式的 “...” を取るため自己参照で記述 0 は自然数である。 もし n が自然数なら、n より1だけ大きいものも、そうである。 ↓ Scheme-style のデータ記述 自然数とはいずれかである 1. 0 または 2. (add1 n)、もし n も自然数なら。 ここで演算 add1 は 自然数に 1 を加えるもの。 (リスト同様、上記の 2 は自己参照を持つが、1は持たない)

14 自然数を定義する(再帰的データ) データ定義から例を組み立てる 0 は最初の自然数。 (add1 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

15 再帰関数のテンプレート リストを処理する関数のテンプレート 自然数を処理する関数のテンプレート
(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) [(zero? n) …] [else … n … (fun-for-natural (sub1 n)) …])) リスト処理の empty? に相当。意味は (= n 0) と同じ リスト処理の rest に相当。意味は (- n 1) と同じ

16 例題3. 自然数処理 n が 0 ならば(終了条件) ：empty (自明な解) そうでなければ：
そうでなければ：　 (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))

17 (naturals 3) から (list 3 2 1) が得られる過程の概略
= … = (cons 3 (naturals 2)) = (cons 3 (cons 2 (naturals 1))) = (cons 3 (cons 2 (cons 1 (naturals 0)))) = (cons 3 (cons 2 (cons 1 empty))) = (list 3 2 1) 最初の式 コンピュータ内部での計算 実行結果

18 練習3. 自然数処理 1から n までの自然数を要素に持つリストを生成する関数 naturals2 を作る naturals2 3
出力は自然数 のリスト1つ 入力は 1つの自然数 3 (list 1 2 3)

19 ヒント 2つの引数を取る補助関数naturals2-subを定義する．
自然な考え方 ヒント 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) ... )

20 n=3の時，(- n 1)は2なので，(list 1 2)
少々難問！ 別の観点から ある数をリストの末尾に置くmake-last-itemを 補助関数として定義し，これを利用する． ;;make-last-item : num (listof num)->(listof num) ;;(make-last-item 3 (list 1 2)) should produce (list 1 2 3) ;;(naturals2 n) ;; もし n=1 ならば (list n) ;; そうでなければ，nを，(naturals2 (- n 1))で作るリストの最後に置く． n=3の時，(- n 1)は2なので，(list 1 2)

21 例題4. 要素の挿入 ソート(整列)されたリストに，整列関係を保って要素を挿入する関数 insert を作る
この例では要素が大きい順に整列されているとする insert 入力は，数と 整列済みのリスト 出力は要素挿入 後の整列済リスト 40 (list ) (list )

22 例題4. 要素の挿入 リスト処理のテンプレートをもとに具体化 リストが空ならば(終了条件) ：
リストが空ならば(終了条件) ：　 (cons n empty) ; 要素が1つのリスト そうでない場合：　整列関係を保つ位置にnを挿入 先頭要素 ≦ n なら→ nが最大なので先頭に挿入 (cons n alon)　が整列済みの結果 先頭要素 ＞ n なら→ nの挿入は尾部のどこか rest部への再帰。その結果と先頭要素を結合 (rest部への再帰的な呼出も意図通りに機能するという前提)

23 例題4. 要素の挿入 No Yes No Yes (empty? lon) (<= (first lon) n)
(cond [(<= (first lon) n) (cons n lon)] [(> (first lon) n) (cons (first lon) (insert n (rest lon)))]) Yes No (<= (first lon) n) Yes (cons n lon) が解 (cons n empty) が解 再帰 (insert n (rest lon))でrest部への挿入を試み、その結果と　(first lon)を結合

24 例題4. 要素の挿入 (define (insert n alon) (cond
;;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 )) = (cons 80 (insert 40 (list )))

25 (insert 20 (list 80 21 10 7 5 4)) から (list 80 21 20 10 7 5 4)) を得る過程の概略
= … = (cons 80 (insert 20 (rest (list )))) = (cons 80 (insert 20 (list ))) = (cons 80 (cons 21 (insert 20 (list ))) = (cons 80 (cons 21 (list ))) = (list )

26 例題5. インサーションソート 例題4の insert を補助関数として使い、リストをソートする関数 sort を作る sort
ここでは，大きい順にソートする 入力はリスト 出力はソート済みリスト sort (list ) (list ) →　(list ) →　(list )

27 例題5.インサーションソート ソート済リストに insert を使って要素を挿入したものもまたソート済リスト
リストが空なら(終了条件) ：　empty　が解 そうでなければ：　要素を1つずつ取り出しながらその時点での整列済みリストを作る →　rest部への再帰呼出の結果に (それが意図通り整列済みリストであるという前提で) first 要素を補助関数 insert で挿入する

28 例題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 (insert (first lon) (sort (rest lon))) empty sort の定義内部に sort の関数適用(再帰的繰り返し) 例：(sort (list )) = (insert 3 (sort (list 5 1 4)))

29 (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 )

30 練習4. インサーションソート 例題5(および例題4)を参考に リストを、今度は小さい順に、ソートする関数 sort2 を作る sort2
入力はリスト 出力はソート済みリスト sort2 (list ) (list ) →　(list ) →　(list )

31 課題

32 課題1. 奇数のリスト 自然数 n から，「1番目からn番目の奇数のリスト」を作る関数 odd_list を作成せよ。

33 Odd-list ;; odd-list: number -> (listof number) ;; (odd-list 4) -> (list ) (define (odd-list n) (cond [(= n 0) empty] [else (cons (- (* 2 n) 1) (odd-list (- n 1)))]))

34 課題2. 構造体リスト処理(フィルタリング) AddressNote 構造体(例題2)についての問題
年齢 an_ageとAddressNote 構造体のリスト a_list を入力とし，年齢が an_age に一致する人のリストを出力する関数 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”))

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