7.5 データ型を使用したプログラミング例

問 7.10

キーと値の組のリストを受け取り，それらを含む辞書を作成する関数

    val makeDict : (string, ’a) list -> ’a dict

を定義し，それを使って辞書を作成し，上記関数のテストを行え．

解答例 makeDict関数の定義例は以下の通り。各関数のテストは省略。

   fun makeDict L =
      foldr
        (fn ((key, v), dict) => enter(key, v, dict))
        Empty
        L

問 7.11

上記の例はキーを string 型に制限されている．この制限を取り除く1つの方法は， string 型の比較演算を直接含む enter と lookUp 関数を定義する代わりに，比較関数を引数として受け取り，enter と lookUp 関数に相当する関数を作り出す，以下の型を持つ高階の関数 makeEnter と makeLookUp を定義することである．

   type (’a,’b) dict = (’a * ’b) tree
   val makeEnter : (’a * ’a -> order) -> ’a * ’b * (’a,’b) dict -> (’a,’b) dict
   val makeLookUp : (’a * ’a -> order) -> ’a * (’a,’b) dict -> ’b

上記の関数を定義し，テストを行え．

解答例 makeEnterの型は、foldlなどと一緒に使うことを考えると、

   val makeEnter : (’a * ’a -> order) -> (’a * ’b) * (’a,’b) dict -> (’a,’b) dict

の方が便利である。そこで、この型の関数として定義例を以下に示す。

   fun makeEnter f ((k, v), Empty) = Node((k,v), Empty, Empty)
     | makeEnter f ((k, v), dict as Node((k’,v’),L,R)) =
       (case f (k,k’) of
           EQUAL => dict
         | GREATER => Node((k’,v’), L, makeEnter f ((k,v), R))
         | LESS => Node((k’,v’), makeEnter f ((k,v),L), R))
   fun makeLookUp f (k, Empty) = NONE
     | makeLookUp f (k, dict as Node((k’,v’),L,R)) =
       (case f (k,k’) of
           EQUAL => SOME v’
         | GREATER => makeLookUp f (k, R)
         | LESS => makeLookUp f (k, L))

問 7.12

makeEnter と makeLookUp を使って， int 型データをキーとし，string 型データを値として持つ (int,string) dict 型の辞書の操作関数を作成し，テストを行え．

解答例 SML#での定義とテストの例を以下に示す。

   # fun enterIntDict x = makeEnter Int.compare x;
   val enterIntDict = fn : [’a. (int * ’a) * (int * ’a) tree -> (int * ’a) tree]
   # fun lookUpIntDict x = makeLookUp Int.compare x;
   val lookUpIntDict = fn : [’a. int * (int * ’a) tree -> ’a option]
   # val D = foldl enterIntDict Empty [(1,"1"), (2, "2"), (3, "3")];
   val D =
     Node
     ((1, "1"), Empty, Node ((2, "2"), Empty, Node ((..., ...), Empty, Empty)))
     : (int * string) tree
   # val items = map (fn x => lookUpIntDict (x, D)) [1,2,3,4]
   val items = [SOME "1", SOME "2", SOME "3", NONE] : string option list