Microsoft PowerPoint - ProD0107.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - ProD0107.ppt"

やすはるごちょう
5 years ago
Views:

1 プログラミング D M 講義資料教科書 :6 章中田明夫 nakata@ist.osaka-u.ac.jp 2005/1/7 プログラミング D -M /1/7 プログラミング D -M- 2 リスト 1 リスト : 同じ型の値の並び val h=[10,6,7,8,~8,5,9]; val h = [10,6,7,8,~8,5,9]: int list val g=[1.0,4.5, 5.6]; val g=[1.0, 4.5, 5.6]: real list val h2=5::h; val h2=[5,10, 6,7,8,~8,5,9]: int list val g2=6.87::g; val g2=[6.87, 1.0, 4.5, 5.6]: real list 2005/1/7 プログラミング D -M- 3 リスト 2 hd と tl hd hd g; val it= 1.0:real hd g2; val it=6.85:real tl g2; val it=[1.0, 4.5, 5.6]: real list 2005/1/7 プログラミング D -M- 4 tl リスト 3 hd [3]; val it=3:int tl [3]; val it=[]: int list hd []; tl []; いずれもエラー []; val it =[]: a list 2005/1/7 プログラミング D -M- 5 リスト : リスト同士の連結 [4,5,6]; val it=[1,2,3,4,5,6]:int list [1]@[2,3,4]; val it=[1,2,3,4]: int list 1@[2,3,4]; エラー 1::[2,3,4]; val it =[1,2,3,4]: int list 2005/1/7 プログラミング D -M- 6 1

2 リスト 5 [] の代わりに nilも可 nil val it=[1,2,3]:int list 一般に [x1,x2,x3,..,xn] = x1::x2::x3:: ::xn::nil 4::3::2::1::nil val it=[4,3,2,1]: int list 2005/1/7 プログラミング D -M- 7 リスト処理関数の例引数のリストを逆順にする関数 reverse reverse([1,2,3]); val it = [3,2,1]: int list reverse([true, true, false]); val it = [false, true, true]: bool list fun reverse = if = nil then nil else reverse (tl [(hd )]; val reverse = fn: a list -> a list # 訳 :reverse は任意の型のリストを引数にとり任意の型但し引数と同じ型のリストを返す関数 2005/1/7 プログラミング D -M- 8 hd reverse の考え方基底段階 =nil の場合そのまま nil を値にすればよい帰納段階 nil の tail がすでにひっくり返っていると仮定するとの head を後ろにもってくれば全体がひっくり返る tail reverse reverse 2005/1/7 プログラミング D -M- 9 nil reverse の等式トレース reverse([1,2,3]) == if [1,2,3]=nil then nil else reverse (tl [(hd [1,2,3])] == [1] == (if [2,3]=nil then nil else reverse(tl [(hd [1] == [1] == (if [3]=nil then nil else reverse(tl [(hd [1] == reverse(nil)@[3]@[2]@[1] == (if nil=nil then nil else reverse(tl [(hd nil)])@[3]@[2]@[1] == == [3,2,1] 2005/1/7 プログラミング D -M- 10 パターンマッチングによるリストの分解リスト処理の基本与えられたリストが空か否か? 空でなければ先頭要素と残りのリストに分解パターンマッチングにより簡潔に記述 case of nil => E1 (h::t) => E2(h,t) E1 : が空のときに返す式 E2(h,t) : が空でないときに返す式 (の先頭要素 hおよび残りのリストtから計算 ) と nil, (h::t) をそれぞれパターンマッチングと一致するようにh,tに値が束縛される 2005/1/7 プログラミング D -M- 11 パターンマッチングによるリストの分解 fun length = case of nil => 0 (h::t) => 1+length t; リストの長さを計算する関数以下の定義とほぼ等価 fun length = if =nil then 0 else 1+length (tl ); ただし型推論によりリストの要素はeqtype =nilよりリストはeqtype リストは要素の型がeqtypeであるときのみeqtype パターンマッチングを使うとリストの要素が eqtype でなくても適用可能 2005/1/7 プログラミング D -M- 12 2

3 パターンマッチングによるリストの分解パターンマッチングを用いない場合 fun length = if =nil then 0 else 1+length (tl ); val length = fn : ''a list -> int length [1.0,2.0,3.0]; エラーメッセージ real list は eqtype ではないのでパターンマッチングによるリストの分解パターンマッチングを用いた場合 fun length = case of nil => 0 (h::t) => 1+length t; val length = fn : 'a list -> int length [1.0,2.0,3.0]; val it = 3 : int 2005/1/7 プログラミング D -M /1/7 プログラミング D -M- 14 case 文 case exp of pat1 => exp1 pat2 => exp2 patn => expn 式 exp とパターン pat1,,patn を順番にパターンマッチングし pati がマッチしたら expi を評価して返す expi 以外は評価されない ( 特殊構文 ) リストのパターン nil 定数変数 pat1::pat2 [pat1,,patn] _ 匿名パターン ( 任意の式にマッチ ) 2005/1/7 プログラミング D -M /1/7 プログラミング D -M- 16 組とリストのパターン fun zip x = case x of (h1::t1,h2::t2) => (h1,h2) :: zip (t1,t2) _ => nil; リストの組 x を組のリストに変換して返す zip ([1,2,3],[4,5,6]); val it = [(1,4),(2,5),(3,6)] 組とリストのパターン fun unzip x = case x of (h1,h2)::t => let val (1,2) = unzip t in (h1::1,h2::2) end _ => (nil,nil); zipの逆変換を行う unzip [(1,4),(2,5),(3,6)]; val it = ([1,2,3],[4,5,6]) 2005/1/7 プログラミング D -M /1/7 プログラミング D -M- 18 3

4 パターンを用いた関数定義 fun 宣言では case 文を省略した以下の記法が使用可 fun f pat1 = exp1 f pat2 = exp2 f patn = expn パターンを用いた関数定義関数式でも case 文を省略した以下の記法が使用可 fn pat1 = exp1 pat2 = exp2 patn = expn case 文を用いた以下の記述と等価 fun f x = case x of pat1 => exp1 pat2 => exp2 patn => expn 2005/1/7 プログラミング D -M- 19 case 文を用いた以下の記述と等価 fn x = case x of pat1 => exp1 pat2 => exp2 patn => expn 2005/1/7 プログラミング D -M- 20 パターンを用いた関数定義例 ) fun length nil = 0 length (h::t) = 1 + length t; 練習問題リストを逆順にして返す関数 reverse をパターンを用いて定義せよ cf.) fun length x = case x of nil => 0 (h::t) => 1 + length t; 2005/1/7 プログラミング D -M /1/7 プログラミング D -M- 22 リスト処理の基本関数 hd : a list -> a リストの先頭要素を返す tl : a list -> a list リストの先頭を除いた残りのリストを返す : a list * a list -> a list 2 つのリストを結合したリストを返す 2 項演算子 ( 右結合結合力 5) リスト処理の基本関数 null : a list -> bool リストが空なら真さもなければ偽を返す rev : a list -> a list リストを逆順にしたものを返す length : a list -> int リストの長さを返す 2005/1/7 プログラミング D -M /1/7 プログラミング D -M- 25 4

5 リスト処理の基本関数 map : ( a -> b)-> a list -> b list 与えられた関数をリストの各要素に適用しその結果のリストを返す集合 A の関数 f による像 f(a) を求める例 ) リストの各要素を 2 倍 map (fn x => x*2) [1,2,3,4]; val it = [2,4,6,8] 2005/1/7 プログラミング D -M- 26 例 : クイックソート qsort [5,4,9,3,6,2,7,5,8] split [4,3,2] [5,5] [9,6,7,8] qsort qsort [2,3, [2,3,4,5,5,6,7,8,9] 2005/1/7 プログラミング D -M- 27 split の実現 fun split(b, nil) = (nil,nil, nil) split(b, x::xs) = let val (S,M,) =split(b, xs); in if b > x then (x::s, M, ) else if b<x then (S, M, x::) else (S, x::m, ) end; val split = fn: int* int list -> int list * int list * int list split(3, [2,1,4,3,5]); val it = ([2,1],[3],[4,5]) : int list * int list * int list クイックソートの実現 fun qsort(nil) = nil qsort(x::xs) = let val (S,M,) = split(x, x::xs); val S = qsort(s); val = qsort(); in S@M@ end; 2005/1/7 プログラミング D -M /1/7 プログラミング D -M- 29 as を使ったパターン fun qsort(nil) = nil qsort(list as x::xs) = let val (S,M,) = split(x, list); val S = qsort(s); val = qsort(); in S@M@ end; nil 2005/1/7 プログラミング D -M /1/7 プログラミング D -M- 31 5

6 nil sum(nil)=0 5 nil sum([5])=5+sum(nil) =5+0=5 2005/1/7 プログラミング D -M /1/7 プログラミング D -M nil sum([3,5]) =3+sum([5]) =3+5=8 2005/1/7 プログラミング D -M nil sum([2,3,5])=2+sum([3,5])=2+8= /1/7 プログラミング D -M- 35 一般的な構造リストがnilならば特定の値 Zを返すリストがh::tの形ならば部分リストtに対する値 Rを再帰的に計算 hとrに対して特定の演算 f(h,r) を適用し得られた結果を返す sum() の場合 : Z=0 f(h,r)=h+r 練習問題以下の各関数に対して対応するZとf(h,R) を与えよ length() null() reverse() map ' [ ヒント :のみに着目する] 2005/1/7 プログラミング D -M /1/7 プログラミング D -M- 37 6

7 汎用のリスト処理関数リスト処理の構造を実現する汎用リスト関数 foldr ( 高階関数 ) fun foldr f Z nil = Z foldr f Z (h::t) = f(h,foldr f Z t); sum() の foldr を使った定義 fun sum = foldr (fn (h,r) => h + R) 0 ; 又は fun sum = foldr (op +) 0 ; 2005/1/7 プログラミング D -M- 40 練習問題以下の各関数を高階関数 foldrを用いて定義せよ length() null() reverse() map g 2005/1/7 プログラミング D -M- 41 7

Programming D 1/15

Programming D 1/15 プログラミング D ML 大阪大学基礎工学部情報科学科中田明夫 nakata@ist.osaka-u.ac.jp 教科書プログラミング言語 Standard ML 入門 6 章 2005/12/19 プログラミング D -ML- 1 2005/12/19 プログラミング D -ML- 2 補足 : 再帰関数の作り方例題 : 整数 x,y( ただし x