i217 関 数 プログラミング 第 6 回 レコードと 組 二 木 厚 吉 緒 方 和 博 レコード(1) いくつかの 値 v 1,,v n をひとまとめにしたデータで, 各 値 v i には 互 いに 異 なるラベルl i が 割 当 てられる. {l 1 = v 1,,l n = v n } このレコードの 型 は, 各 viの 型 をt i とすると, {l 1 :t 1,,l n :t n } である. ラベルl i が 割 当 てられた 値 v i は,セレクタ#l i により 取 出 す ことができる. - val ti1 = {key="area",value=56}; val ti1 = {key = "area", value = 56} : {key : string, value : int} - #value ti1; val it = 56 : int 2
レコード(2) レコードの 要 素 (フィールド)の 並 び 順 には 意 味 はない. {key:string,value:int} {value:int,key:string} と は 同 じ 型 である. {key= area,value=56} {value=56,key= area } と は 同 じ 値 (レコード)である. 3 レコードパターン 例 : - val {key=x,value=y} = ti1; val x = "area" : string val y = 56 : int - val {value=y,key=x} = ti1; val y = 56 : int val x = "area" : string - val {key,value} = ti1; val key = "area" : string val value = 56 : int - val {key=x,...} = ti1; val x = "area" : string 4
テーブルの 再 実 装 (1) レコードのリストでテーブルを 再 実 装 する. レコード 型 のtype 宣 言 : type ('a,'b) table = {key:'a,value:'b} list 空 テーブルの 表 現 : val empty = [] エントリの 作 成 : fun mkentry (a,b) = {key=a,value=b} 単 一 エントリから 成 るテーブルの 作 成 : fun singleton (a,b) =[mkentry (a,b)] 5 テーブルの 再 実 装 (2) エントリの 更 新 追 加 : fun update (a,b,[]) = [mkentry (a,b)] update (a,b,{key,value}::t) = if a=key then (mkentry (a,b))::t else (mkentry (key,value)) ::(update (a,b,t)) 鍵 が 登 録 されているかどうかの 確 認 : fun iskey (a,t) = List.exists (fn {key,value} => key=a) t 6
テーブルの 再 実 装 (3) エントリの 削 除 : fun delete (a,[]) = [] delete (a,{key,value}::t) = if a=key then t else (mkentry(key,value))::delete(a,t) 鍵 の 値 の 取 出 し( 未 登 録 場 合 例 外 発 生 ): fun getval (a,[]) = raise Table getval (a,{key,value}::t) = if a=key then value else getval (a,t) fold 関 数 : fun fold f e t = foldl (fn ({key,value},c) => f(key,value,c)) e t tolist 関 数 : fun tolist t = t 7 テーブルの 再 実 装 (4) 再 実 装 におけるテーブルのシグネチャ: signature TABLE1 = sig exception Table type ('a,'b) table val empty : (''a,'b) table val singleton : (''a*'b) -> (''a,'b) table val update : ( a* b*(( a, b) table)) -> (''a,'b) table val iskey : (''a*((''a,'b) table)) -> bool val delete : (''a*((''a,'b) table)) -> (''a,'b) table val getval : (''a*((''a,'b) table)) -> 'b val lookup : (''a*((''a,'b) table)) -> 'b option val fold : ((''a*'b*'c) -> 'c) -> 'c -> ((''a,'b) table) -> 'c val tolist : ( a, b) table -> {key:''a,value:'b} list end 8
テーブルの 再 実 装 (5) 再 実 装 におけるテーブルのストラクチャ: structure Table1 :> TABLE1 = struct exception Table type ('a,'b) table = {key:'a,value:'b} list val empty = [] fun mkentry (a,b) = {key=a,value=b} fun singleton (a,b) =[mkentry (a,b)] fun update (a,b,[]) = [mkentry (a,b)] update (a,b,{key,value}::t) = if a=key then (mkentry (a,b))::t else (mkentry (key,value))::(update (a,b,t)) end 9 テーブルの 再 実 装 (6) シグネチャを 指 定 して 作 ったストラクチャでは,シグネチャで 仕 様 が 記 述 されていないものは 隠 蔽 される. 例 : - Table.mkEntry ("area",56); stdin:513.51-514.15 Error: unbound variable or constructor: mkentry in path Table1.mkEntry 10
請 求 書 作 成 支 援 の 再 実 装 (1) 用 いる 型 に 名 前 を 付 ける. type articlecode = string type articletag = {name:string,price:int} type cartitem = {code:articlecode,no:int} type billitem = {name:string,no:int,subtotal:int} type bill = {details:(billitem list),total:int} 商 品 ( 値 札 )タグの 作 成 : fun mkatag (n,p) = {name=n,price=p} 空 の 商 品 目 録 作 成 : val emptycatalog = empty 11 請 求 書 作 成 支 援 の 再 実 装 (2) 商 品 の 目 録 への 追 加 : fun putarticle (c,n,p,cat) = update(c,mkatag (n,p),cat) 商 品 目 録 作 成 例 : val catalog = putarticle ("o1","orange",90, putarticle ("t2","tomato(l)",150, putarticle ("a1","apple",90, putarticle ("t1","tomato(m)",120, emptycatalog)))) 12
請 求 書 作 成 支 援 の 再 実 装 (3) ショッピングカートの 要 素 の 作 成 : fun mkcitem (c,n) = {code=c,no=n} 空 のショッピングカートの 作 成 : val emptycart = [] ショッピングカートへの 要 素 の 追 加 : fun putitem (c,n,sc) = (mkcitem (c,n))::sc ショッピングカートの 作 成 例 : val cart = putitem("t2",2, putitem("a1",3, putitem("o1",2, putitem("a1",7,emptycart)))) 13 請 求 書 作 成 支 援 の 再 実 装 (4) 請 求 書 の 明 細 の 項 目 作 成 : fun mkbitem (n,m,st) = {name=n,no=m,subtotal=st} 請 求 書 作 成 の 補 助 関 数 : fun submkbill cat [] t = t submkbill cat ({code,no}::sc) t = case lookup (code,cat) of NONE => raise Catalog SOME {name,price} => (case lookup (code,t) of NONE => submkbill cat sc (update (code,mkbitem (name,no,no*price),t)) SOME {name,no=n2,subtotal} => submkbill cat sc (update (code, mkbitem (name,no+n2,no*price+subtotal),t))) 14
請 求 書 作 成 支 援 の 再 実 装 (5) テーブルに 登 録 されている 値 のリスト 作 成 : fun listofvalues [] = [] listofvalues ({key,value}::t) = value::(listofvalues t) 合 計 の 計 算 : fun total t = fold (fn (_,{name,no,subtotal},b) => subtotal+b) 0 t 請 求 書 作 成 : fun mkbill cat sc = let val t = submkbill cat sc empty in (listofvalues t,total t) end 15 N 項 組 n 個 の 要 素 から 成 る 組 (n 項 組 ) (a 1,,a n ) は,1からnまでの 整 数 をラベルとするレコード {1=a 1,,n=a n } である, したがって 以 下 のようになる. - {1= #"a",2 = true,3 = 0}; val it = (#"a", true, 0) : char * bool * int - (#"a",true,0) = {2 = true,3 = 0,1= #"a"}; val it = true : bool - #2 (#"a",true,0); val it = true : bool 16
練 習 問 題 (1) 1. レコードのリストによるテーブルの 実 装 における,シグネチャTABLE1に 関 数 insertとremoveの 仕 様 を 追 加 したシグネチャTABLE2を 作 り,ストラクチャ Table1にinsertとremoveの 定 義 が 追 加 され,シグネチャTABLE2で 不 透 明 に 制 約 されたストラクチャTable2を 作 れ. 2. 請 求 書 作 成 のためのシグネチャBILLは 以 下 のように 定 義 できる. signature BILL = sig type articlecode type articletag type cartitem type billitem type bill exception Catalog val emptycatalog : (articlecode,articletag) Table.table val putarticle : string*string*int* ((articlecode,articletag) Table.table) -> ((articlecode,articletag) Table.table) 17 練 習 問 題 (2) val emptycart : cartitem list val putitem : string*int*(cartitem list) -> (cartitem list) val mkbill : ((articlecode,articletag) Table.table) -> (cartitem list) -> bill val printcatalog : ((articlecode,articletag) Table.table) -> ({key:string,value:{name:string,price:int}} list) val printcart : (cartitem list) -> ({code:string,no:int} list) val printbill : bill -> {details:({name:string, no:int,subtotal:int} list), total:int} end 18
練 習 問 題 (3) シグネチャBILLで 不 透 明 に 制 約 して 作 られるストラクチャBillを 作 成 せよ ストラクチャTable1を 用 いること printcatalog printcartおよびprintbillは テーブルにお ける 関 数 tolistに 相 当 するもので それぞれ 商 品 目 録 ショッピン グカートおよび 請 求 書 の 内 容 を 表 示 する 関 数 である ヒント1:ストラクチャTable1で 用 意 されている 関 数 を 用 いる 場 合 は Table1.をつけること ヒント2: 関 数 listofvaluesの 引 数 の 型 はリストであり テーブルで はない このため tolistを 使 って テーブルからリストに 変 換 する 必 要 がある 19