プログラミング D M 講義資料 教科書 :6 章 中田明夫 nakata@ist.osaka-u.ac.jp 2005/1/7 プログラミング D -M- 1 2005/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 @ : リスト同士の連結 [1,2,3] @ [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
リスト 5 [] の代わりに nilも可 [1,2,3] @ 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 [1,2,3]) @ [(hd [1,2,3])] == reverse([2,3]) @ [1] == (if [2,3]=nil then nil else reverse(tl [2,3]) @ [(hd [2,3])]) @ [1] == reverse([3]) @ [2] @ [1] == (if [3]=nil then nil else reverse(tl [3]) @ [(hd [3])]) @ [2] @ [1] == reverse(nil)@[3]@[2]@[1] == (if nil=nil then nil else reverse(tl nil) @ [(hd nil)])@[3]@[2]@[1] == 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
パターンマッチングによるリストの分解 パターンマッチングを用いない場合 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- 13 2005/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- 15 2005/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- 17 2005/1/7 プログラミング D -M- 18 3
パターンを用いた関数定義 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- 21 2005/1/7 プログラミング D -M- 22 リスト処理の基本関数 hd : a list -> a リストの先頭要素を返す tl : a list -> a list リストの先頭を除いた残りのリストを返す infixr 5 @ @ : 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- 24 2005/1/7 プログラミング D -M- 25 4
リスト処理の基本関数 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, 4] [6,7,8,9] @ @ [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- 28 2005/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; 2 3 5 nil 2005/1/7 プログラミング D -M- 30 2005/1/7 プログラミング D -M- 31 5
nil sum(nil)=0 5 nil sum([5])=5+sum(nil) =5+0=5 2005/1/7 プログラミング D -M- 32 2005/1/7 プログラミング D -M- 33 3 5 nil sum([3,5]) =3+sum([5]) =3+5=8 2005/1/7 プログラミング D -M- 34 2 3 5 nil sum([2,3,5])=2+sum([3,5])=2+8=10 2005/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 g @ ' [ ヒント :のみに着目する] 2005/1/7 プログラミング D -M- 36 2005/1/7 プログラミング D -M- 37 6
汎用のリスト処理関数 リスト処理の構造を実現する汎用リスト関数 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