PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

しょうこむらかわ
4 years ago
Views:

1 練習問題 8 の解答例プログラミング D 大阪大学基礎工学部情報科学科中田明夫 nakata@ist.osaka-u.ac.jp プログラミング D -ML- 1 次の関数の型を推論しその理由を説明せよ fun foo (a,b,c,d:real) = if a<b then c else if a>b then c else d; 引数 a,b,c,dの型をそれぞれ 'a,'b,'c,'dとおく関数 fooの型は ('a*'b*'c*'d)->'eとおける(fooの返り値の型を'eとおいた) 明示的な型宣言 d:real より 'd=real if then c else d より'c='d fooの返り値はcまたはdなので 'e='c='d a<b より'a='bかつ 'a,'bはint,real,char,string(,word) のいずれかこれ以上型を特定できないので 'a='b=int 以上より fooの型は (int*int*real*real)->real プログラミングD -ML- 2 練習問題 8 の解答例次の関数の型を推論しその理由を説明せよ fun f g h x = (g x) (h x:int); f の引数 g,h,x の型をそれぞれ 'a,'b,'c とおく fの型は 'a->'b->'c->'dとおける (fの返り値の型を'dとおいた) (g x) より gはxを引数にとる関数すなわち 'a='c->'e (g の返り値の型を 'eとおいた) (h x) より hも同様すなわち 'b='c->'f (hの返り値の型を 'fとおいた) h x:int より'f=int ( 型宣言の結合力は関数適用より弱い ) 後は練習問題 7と同様にして関数 fの型は ('c->(int->'g))- >('c->int)->'c->'g 型変数名を整理すると ('a->(int->'b))->('a->int)->'a->'b プログラミングD -ML- 3 練習問題 9 の解答例次の関数の型を推論しその理由を説明せよ fun foo (a,b,c,d) = if a=b then c else d; a,b,c,d の型を 'a,'b,'c,'d とおく関数 foo の型を ('a*'b*'c*'d)->'e とおく a=b より 'a='b かつ 'a,'b は eqtype なのでそれぞれ ''a,''b と書く if then c else d より 'c='d foo の返り値は c または d なので 'e='c='d これ以上型を特定できないので foo の型は (''a*''a*'c*'c)->'c 型変数名を整理すると (''a*''a*'b*'b)->'b プログラミング D -ML- 4 練習問題 10 の解答例引数 exp が与えられたとき exp を評価してその結果を捨てて unit 型の値を返す関数 ignore を定義せよヒント 1: 関数の引数は関数実行前に ( 勝手に ) 評価されるヒント 2:unit 型を返すときは () を返せばよい fun ignore x = (); プログラミング D -ML- 5 練習問題 11 の解答例以下の式の実行結果および返り値を予想せよ if 1>0 then print "1 n" else print "0 n"; 実行結果 :"1" および改行が表示される返り値 : () : unit true andalso (false before print "abc n"); 実行結果 : "abc" および改行が表示される返り値 : false false andalso (true before print "def n"); 実行結果 : 何も表示されない (print 関数は実行されない ) 返り値 : false false orelse (false before print "ghi n") andalso (true before print "jkl n"); 実行結果 :"ghi" および改行が表示される返り値 :false プログラミングD -ML- 6

2 練習問題 12 の解答例以下の式を順に実行したとしたとき各変数に束縛される値とその型を予想せよ val a = { Name="Joe", Age=21 }; val b = (2,3); val {Age=c, } = a; val d=(#name a); val (e,f)=b; val {2=g, } = b; val h=(#1 b); {a {Age=21,Name="Joe"}, b (2,3), c 21, d "Joe", e 2, f 3, g 3, h 2} プログラミング D -ML- 7 練習問題 13 の解答例リストを逆順にして返す関数 reverse をパターンを用いて定義せよ fun reverse nil = nil reverse (h::t) = reverse(t)@[h]; プログラミング D -ML- 8 練習問題 14 の解答例以下の各関数に対して対応する Z と f(h,r) を与えよ length(l) Z=0 f(h,r)=1+r null(l) Z=true f(h,r)=false reverse(l) Z=nil f(h,r)=r@[h] 練習問題 14 の解答例以下の各関数に対して対応する Z と f(h,r) を与えよ map g L Z=nil f(h,r)=g(h)::r L' Z=L' f(h,r)=h::r プログラミング D -ML- 9 プログラミング D -ML- 10 練習問題 15 の解答例以下の各関数を高階関数 foldr を用いて定義せよ fun length L = foldr (fn (_,R)=>1+R) 0 L; fun null L = foldr (fn (_,_) => false) true L; fun reverse L = foldr (fn (h,r)=>r@[h]) nil L; fun map g L = foldr (fn (h,r)=>g(h)::r) nil L; 練習問題 16 教科書 7.5 節の辞書プログラムに指定したキーに一致するデータを削除する関数 remove(key,dict): string*'a dict -> 'a dict を追加せよプログラミング D -ML- 11 プログラミング D -ML- 12

3 練習問題 16 の解答例 fun remove(key,dict) = case dict of Empty => dict Node((key',v),L,R) => if key=key' then (if R=Empty then L else let val ((key'',z),r')=removemin R in Node((key'',z),L,R') end) else if key<key' then remove(key,l) else remove(key,r); 練習問題 16 の解答例 exception EmptyTree; fun removemin dict = case dict of Empty => raise EmptyTree Node((key,v),Empty,R) => ((key,v),r) Node((key,v),L,R) => let val ((key',z),l')=removemin L in ((key',z),node((key',z),l',r)); プログラミング D -ML- 13 プログラミング D -ML- 14 練習問題 17 の解答例与えられたリスト L の n 番目の要素を返す関数 nth n L : int -> 'a list -> 'a を定義せよただし返り値が存在しない場合は例外 Undefined を発生するようにせよ ML exception Undefined; fun nth _ nil = raise Undefined nth 1 (h::_) = h nth n (_::t) = if n<=0 then raise Undefined else nth (n-1) t; 教科書 :15 章入出力処理プログラミング D -ML- 15 プログラミング D -ML- 16 ファイルからの読み込み : 基本形ファイルからの読み込み : N 文字単位で読み込む (* structure TextIO をオープン *) val infile = openin " ファイル名 "; val infile = -: instream 何か処理 closein infile; TextIO.openIn filename : filename で指定したファイルをオープンし instream 型の値 (C 言語でのファイルポインタに相当 ) を返す TextIO.closeIn infile : infile(instream 型 ) をクローズする TextIO.endOfStream infile : ファイル infile の最後なら true を返す関数 TextIO.inputN (infile, n) : n 個の文字を読んで文字列として返すプログラミング D -ML- 17 fun readlist infile = if endofstream infile then nil else (inputn (infile, 2)) :: (readlist infile); - readlist (openin "test"); open TextIO にともなう膨大なメッセージ val it = ["aa", "a n", "bb", " na", " n"] : vector list (* 型 TextIO.vector は string の別名 *) % cat test aaa bb a プログラミング D -ML- 18

4 ファイルからの読み込み : 行単位で読み込むファイルからの読み込み : ファイル全体を文字列として読み込む fun readlist infile = if endofstream infile then nil else (inputline infile) :: (readlist infile); readlist (openin "test"); open TextIO にともなう膨大なメッセージ val it = ["aaa n", "bb n", "a n"] : string list % cat test aaa bb a プログラミング D -ML- 19 val s= input (openin test ); (* TextIO.input 関数を使用 *) open TextIO にともなう膨大なメッセージ val s = aaa nbb na n : vector % cat test aaa bb a プログラミング D -ML- 20 ファイルからの 1 文字読み込み TextIO.input1 関数 : ファイルから ( もし可能なら )1 文字読み込み char option 型を返す ( 教科書 p.100 a option 型参照 ) end of stream ならば NONE を返す fun readlist infile = case input1 infile of SOME c => c :: (readlist infile) _ => nil; readlist (openin "test"); val s = [#"a", #"a", #"a", #" n", #"b", #"b", #" n", #"a", #" n"] : elem list (* 型 TextIO.elem は char の別名 *) ファイルからの 1 文字先読み TextIO.lookahead 関数 : ファイルから ( もし可能なら )1 文字先読み ( ファイルの読み込み位置を進めない以外は TextIO.input1 関数と同じ ) (* 空白を読み飛ばす関数 skipspaces ( 教科書 p.192 参照 ) *) fun skipspaces infile = case lookahead infile of SOME c => if Char.isSpace c then (input1 infile; skipspaces infile) else () _ => (); Char.isSpace 関数 : 引数がスペースであれば true さもなければ false を返す ( モジュール Char 内 ) プログラミング D -ML- 21 プログラミング D -ML- 22 ファイルへの書き込み : 基本形標準入出力 val outfile = openout " ファイル名 "; (* 書き込み用にファイルをオープン *) val outfile = -: outstream 何か処理 closeout outfile; TextIO.stdIn : 標準入力 (instream 型 ) TextIO.stdOut: 標準出力 (outstream 型 ) TextIO.stdErr : 標準エラー出力 (outstream 型 ) openappend も可 (* 追記用オープン *) output (outfile, string): outfile に文字列 string を出力 ( 返り値は無し (unit 型 )) プログラミング D -ML- 23 プログラミング D -ML- 24

5 fun put 0 = output (stdout, " n") put n = (output(stdout, "X"); put (n-1) ); (* 1 行に n 個の X を標準出力に書き込む関数 put n *) fun fact n = (put n; if n=0 then 1 else n*fact(n-1)); -fact 5; XXXXX XXXX XXX XX X ファイルへの書き込み val it=120:int プログラミング D -ML- 25 プログラム例 : 単語の読み込み (* 空白で区切られたアルファベットと数字からなる単語を1つ読み込む関数 getword ( 教科書 p.192 getid 関数の変形 ) *) fun skipspaces infile = ; (* 空白を読み飛ばす関数 skipspaces *) fun getword infile = let fun getrest s = case lookahead infile of SOME c => if Char.isAlphaNum c then getrest (s ^ inputn(infile,1)) else s _ => s; in (skipspaces infile; getrest "") end; Char.isAlphaNum 関数 : 引数がアルファベットか数字であればtrue, さもなければfalseを返す関数 ( モジュールChar 内 ) プログラミング D -ML- 26 プログラム例 : カンマ区切りデータの読み込み (* カンマ又は改行で区切られた文字列を 1 つ読み込む関数 getcsv ( 教科書 p.192 getid 関数の変形 ) *) ML fun skipspaces infile = ; (* 空白を読み飛ばす関数 skipspaces *) fun getcsv infile = let fun getrest s = case lookahead infile of SOME c => if not ((c = #",") orelse (c = #" n")) then getrest (s ^ inputn(infile,1)) else (input1 infile; s) _ => s; in (skipspaces infile; getrest "") end; プログラミング D -ML- 27 教科書 :7.6 節 +α 遅延評価と無限データ型プログラミング D -ML- 28 関数の評価方法多くのプログラム言語引数を先に求めてから関数値を計算 ( 評価 ) call-by-value 一般に先行評価 (eager evaluation) という引数を後で必要になってから求めるという考え方もある call-by-name, call-by-need 一般に遅延評価 (lazy evaluation) という先行評価 (call-by-value) fun double x = x*x; (double 2+2) == (double 4) 引数を先に評価 == (4*4) 関数 doubleを評価 == 16 演算子 * を評価プログラミング D -ML- 29 プログラミング D -ML- 30

6 遅延評価 (call-by-name) fun double x = x*x; (double 2+2) == ((2+2)*(2+2)) 関数 doubleを評価 == (4*4) ( 演算子 * の評価のためにに必要になったので ) 引数の式を評価 == 16 演算子 * を評価先行評価と遅延評価の関係以下の結果が知られている定理 [Church and Rosser] 純粋な関数型言語においてもし先行評価と遅延評価それぞれの評価方法でもし共に評価結果が求まったならばそれらは同じ値となる純粋な関数型言語において遅延評価では必ず評価結果を求めることが出来るが先行評価では求められないような式が存在するプログラミング D -ML- 31 プログラミング D -ML- 32 遅延評価の特徴利点 1 必要な計算だけを行うことが可能使用されなかった引数は評価しなくてよいもしある引数を求める計算が停止しなければその引数を関数本体で使用しないなら計算しなくてよい全体の計算は停止遅延評価の特徴利点 2 無限個の要素を持つデータ型 ( 無限データ型 ) を扱うことが可能各要素の値そのものを記憶する代わりに値を求める関数として記憶必要になった時点で計算以下のようなプログラムを簡潔に記述可能任意番目の素数を求めるある値を任意の精度で求める無理数の値を任意の n に対して小数点以下 n 桁まで求めるなどプログラミング D -ML- 33 プログラミング D -ML- 34 遅延評価の特徴欠点効率の良い実装が困難同じ計算を何度も実行してしまうなど副作用 ( 代入入出力など ) をうまく扱えない実際にいつ評価されるのか一般に予測困難理論的には興味深く現在も研究がなされている Haskell: 遅延評価を採用した関数型言語 ML における遅延評価 MLは原則として先行評価例外 :if-then-else andalso orelse case 文など ( 特殊構文 ) ある工夫をすれば MLでも遅延評価の実現が可能プログラミング D -ML- 35 プログラミング D -ML- 36

7 ML における遅延評価式 exp の代わりに unit 型から exp への関数を考える type a delayed = unit -> a; 遅延された型 a a delayed 型の式の例 val x:int delayed = fn () => 2+2; val x=fn : int delayed ML における遅延評価 type a delayed = unit -> a; val x:int delayed = fn () => 2+2; val x=fn : int delayed 関数式 (fn => ) 自体は単なる値に過ぎないのでそれ以上評価されない遅延された値を評価したいとき関数として呼び出す x(); val it=4:int 引数はunit 型の値 () プログラミング D -ML- 37 プログラミング D -ML- 38 ML における遅延評価 fun force d = d (); a delayed 型の式 d を引数に取りそれを強制的に評価し結果の値を返す同様に式 d を a delayed 型に変換する関数 delay も定義したいが fun delay d = fn () => d; この関数は期待した動作はしない delay の引数 d が先に評価されてしまうので delay(exp) の代わりに fn () => exp と書くことにする先行評価を遅延評価に変換 fun f x= x x (* 関数 f の定義 *) fun f x= (force x) (force x) (* f の遅延評価バージョン *) (f exp) (* 関数 f の呼び出し *) (f (fn ()=>exp)) (* f の呼び出しの遅延評価バージョン *) プログラミング D -ML- 39 プログラミング D -ML- 40 遅延評価の応用 : 無限リスト教科書 7.6 節無限リスト型 a inflist の宣言 datatype a inflist = NIL CONS of a * ( a inflist delayed); NIL : 空の無限リスト CONS(x,L) : 先頭要素がx 2 番目以降のリストがLであるような無限リスト [a1,a2, ]=CONS(a1,[a2, ]) リストの2 番目以降の値の評価を遅らせる無限リストを返す関数 n から始まる整数の無限リスト [n,n+1,n+2, ] を返す関数 fun FROMN n = CONS(n, fn () => FROMN (n+1)); 1 と 0 を交互に繰り返す無限リスト [1,0,1,0, ] を返す関数 fun oneszeros ()= CONS(1, fn () => CONS(0,oneszeros)); プログラミング D -ML- 41 プログラミング D -ML- 42

8 無限リストの操作関数 inflistの操作関数 fun HD(CONS(a,b))=a; 無限リストの先頭要素を返す fun TL(CONS(a,b))=b(); 無限リストの先頭要素を除いたリストを返す fun NULL NIL = true NULL _= false; 無限リストが空ならば真さもなければ偽を返す fun NTH 0 L = HD L NTH n L = NTH (n-1) (TL L); 無限リストのn 番目の要素を返す ( 先頭は0 番目と数える ) 無限リスト : 実行例 HD (FROMN 1); val it=1:int NTH 3 (FROMN 1); val it=4:int NTH 3 (oneszeros()); val it=0:int NTH 4 (oneszeros()); val it=1:int プログラミング D -ML- 43 プログラミング D -ML- 44 無限リスト : 実行例 NTH 3 (FROMN 1) の等式トレース == NTH 3 CONS(1, fn () => FROMN 2) == NTH 2 (TL CONS(1, fn () => FROMN 2))) == NTH 2 ( (fn () => FROMN 2) () ) == NTH 2 (FROMN 2) == NTH 2 CONS(2, fn () => FROMN 3) == NTH 1 (TL CONS(2, fn () => FROMN 3) == NTH 1 (FROMN 3) fun HD(CONS(a,b))=a; fun TL(CONS(a,b))=b(); fun NTH 0 L = HD L NTH n L = NTH (n-1) (TL L); fun FROMN n = CONS(n, fn () => FROMN (n+1)); 無限リスト : 実行例 == NTH 1 (FROMN 3) == NTH 1 CONS(3, fn () => FROMN 4) == NTH 0 (TL CONS(3, fn () => FROMN 4) == NTH 0 (FROMN 4) == NTH 0 CONS(4, fn () => FROMN 5) == HD CONS(4, fn () => FROMN 5) == 4 fun HD(CONS(a,b))=a; fun TL(CONS(a,b))=b(); fun NTH 0 L = HD L NTH n L = NTH (n-1) (TL L); fun FROMN n = CONS(n, fn () => FROMN (n+1)); プログラミング D -ML- 45 プログラミング D -ML- 46 練習問題 23 NTH 3 (oneszeros()) の等式トレースを示せ fun HD(CONS(a,b))=a; fun TL(CONS(a,b))=b(); fun NTH 0 L = HD L NTH n L = NTH (n-1) (TL L); fun oneszeros ()= CONS(1, fn () => CONS(0,oneszeros)); 無限リストの操作関数 : 条件を満たす要素を抽出 inflist の操作関数 fun FILTER f L= if NULL L then NIL else if f(hd L) then CONS(HD L, fn () => (FILTER f (TL L))) else FILTER f (TL L); 無限リストLの要素のうち f(x) が真となる要素 xのみを取り出した無限リストを返す関数 FILTER プログラミング D -ML- 47 プログラミング D -ML- 48

9 無限リストの操作関数 : 有限個の要素を取り出す inflist の操作関数 ( 教科書問 7.14) 最初の n 個の要素を除いたリストを返す関数 DROP fun DROP 0 L = L DROP n L= ; 最初のn 個の要素を通常のリストにして返す関数 TAKE fun TAKE 0 L = nil TAKE n L = (HD L):: ; n 番目から始まるm 個の要素を通常のリストにして返す関数 VIEW fun VIEW (n,m) L = ; DROP と TAKE を用いれば容易に定義可能プログラミング D -ML- 49 無限リストの応用例 : 素数リスト fun SIFT NIL = NIL SIFT L = let val a = HD L in CONS(a, fn () => SIFT (FILTER (fn x => (x mod a) <>0) (TL L))) end; val PRIMES = SIFT (FROMN 2); VIEW (100,10) PRIMES; val it = [541,547,557,563,569,571,577,587,593,599] : int list (* 100 番目 ~109 番目の素数のリスト *) プログラミング D -ML- 50

Microsoft PowerPoint - ProD0107.ppt

Microsoft PowerPoint - ProD0107.ppt プログラミング 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,