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

Slides:



Advertisements
Similar presentations
0章 数学基礎.
Advertisements

プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
Fortran と有限差分法の 入門の入門の…
プログラミング言語としてのR 情報知能学科 白井 英俊.
第11回 整列 ~ シェルソート,クイックソート ~
第13回構造体.
第12回構造体.
2009/10/9 良いアルゴリズムとは 第2講: 平成21年10月9日 (金) 4限 E252教室 コンピュータアルゴリズム.
第10回 ソート(1):単純なソートアルゴリズム
情報工学概論 (アルゴリズムとデータ構造)
第6章 2重ループ&配列 2重ループと配列をやります.
条件式 (Conditional Expressions)
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
プログラミング論 II 電卓,逆ポーランド記法電卓
アルゴリズムとデータ構造 第2回 線形リスト(復習その2).
Tokuda Lab. NISHIMURA Taichi
ML 演習 第 7 回 新井淳也、中村宇佑、前田俊行 2011/05/31.
第11回 整列 ~ シェルソート,クイックソート ~
構造体 構造体, 構造体とポインタの組み合わせ,.
7.プログラム設計法と 種々のエラー.
二分探索木によるサーチ.
第7回 条件による繰り返し.
Cプログラミング演習 中間まとめ2.
データ構造とアルゴリズム 第4回 リスト ~ データ構造(1)~.
PROGRAMMING IN HASKELL
PROGRAMMING IN HASKELL
繰り返し計算 while文, for文.
アルゴリズムとプログラミング (Algorithms and Programming)
10.構造体とグラフィックス.
第7回 条件による繰り返し.
12.数値微分と数値積分.
6.リストの生成.
逐次プログラムの正当性(2) 帰納的アサーション法(フロイド法)
8. 高階関数を用いた抽象化 プログラミング論I.
データ構造と アルゴリズム 第五回 知能情報学部 新田直也.
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとプログラミング (Algorithms and Programming)
3.条件式.
プログラミング基礎B 文字列の扱い.
プログラミング 4 整列アルゴリズム.
4.リスト,シンボル,文字列.
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
11.再帰と繰り返しの回数.
9.構造体.
6.データ構造入門 6-1.連結リスト(Linked List) 6-2.スタック(Stack) 6-3.キュー(Queue)
15.cons と種々のデータ構造.
プログラミング入門2 第9回 ポインタ 情報工学科 篠埜 功.
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
統計ソフトウエアRの基礎.
2.関数の組み合わせ によるプログラム.
情報工学概論 (アルゴリズムとデータ構造)
PROGRAMMING IN HASKELL
情報処理Ⅱ 第7回 2004年11月16日(火).
~sumii/class/proenb2009/ml6/
5. 任意長の合成データ:リスト プログラミング論I.
PROGRAMMING IN HASKELL
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
PROGRAMMING IN HASKELL
関数と再帰 教科書13章 電子1(木曜クラス) 2005/06/22(Thu.).
データ構造と アルゴリズム 第四回 知能情報学部 新田直也.
7. 設計の抽象化 プログラミング論 I.
情報処理Ⅱ 2005年11月25日(金).
第10回 関数と再帰.
プログラミング入門2 第3回 条件分岐(2) 繰り返し文 篠埜 功.
4. 合成データ:構造体 プログラミング論I.
TList リスト構造とは? 複数のデータを扱うために、 データの内容と、次のデータへのポインタを持つ構造体を使う。
計算技術研究会 第5回 C言語勉強会 関数(function)を使う
プログラミング言語論 プログラミング言語論 演習7 解答と解説 演習7 解答と解説 1.
9. 再帰のバリエーション (生成的再帰) プログラミング論 I.
高度プログラミング演習 (10).
Presentation transcript:

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

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

リスト処理の再帰関数のテンプレート リスト処理関数一般のテンプレート 今回の関数 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つのリスト (ベクトル)を処理 する必要がある

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

例題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)))

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

例題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")

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

例題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で結合し て結果リストを作る

C言語

練習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 35 30 28) 次に AddressNote 構造体のリストから,年齢(age)の 平均を求める関数 average_age を作る

例題3. 自然数処理 n から 1 までの自然数を要素に持つリストを生成する関数 naturals を作る naturals 3 出力は自然数 のリスト1つ 入力は 1つの自然数 3 (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) は次の自然数。 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) [(zero? n) …] [else … n … (fun-for-natural (sub1 n)) …])) リスト処理の empty? に相当。意味は (= n 0) と同じ リスト処理の rest に相当。意味は (- n 1) と同じ

例題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))

(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) 最初の式 コンピュータ内部での計算 実行結果

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

ヒント 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) ... )

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)

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

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

例題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)を結合

例題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 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)) を得る過程の概略 = … = (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 ここでは,大きい順にソートする 入力はリスト 出力はソート済みリスト sort (list 3 5 1 4) (list 1 3 5 7 10 21 4 80) → (list 5 4 3 1) → (list 80 21 10 7 5 4 3 1)

例題5.インサーションソート ソート済リストに insert を使って要素を挿入したものもまたソート済リスト リストが空なら(終了条件) : empty が解 そうでなければ: 要素を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 (insert (first lon) (sort (rest lon))) empty sort の定義内部に sort の関数適用(再帰的繰り返し) 例:(sort (list 3 5 1 4)) = (insert 3 (sort (list 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 入力はリスト 出力はソート済みリスト sort2 (list 3 5 1 4) (list 7 1 80 3 21 5 10 4) → (list 1 3 4 5) → (list 1 3 4 5 7 10 21 80)

課題

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

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 “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 ;;(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) ] ))