プログラミング言語 Standard ML 入門 (問題の解答例)

9.3 例外を使ったプログラミング

問 9.2

関数 enter での辞書の登録に際して，すでに同一名のキーが登録されていたら例外 DuplicateEntry を発生させるように変更せよ．

解答例

   exception DuplicateEntry
   fun enter (key,v,dict) =
       case dict of
            Empty => Node((key,v),Empty,Empty)
          | Node((key’,v’),L,R) =>
              if key = key’ then raise DuplicateEntry
              else if key > key’ then
                   Node((key’,v’),L, enter (key,v,R))
              else Node((key’,v’),enter (key,v,L),R)

問 9.3

int list 型データに含まれる値の積を求める関数を書け．ただしその中で，もしリストの途中に $0$ が見つかったら処理を中断して，ただちに $0$ を返すような処理を，例外を使って実現せよ．

解答例

   fun prodList L =
     let
       exception Zero
       fun f nil r = r
         | f (0::t) r = raise Zero
         | f (h::t) r = f t (h * r)
     in
       f L 1
       handle Zero => 0
     end

問 9.4

makeMemoFun を使って作ったフィボナッチ関数と上記の fastFib を両方定義し，その速度を比較せよ．

解答例 SML#でコンパイルし時間計測をする手順も含め説明する。

makeMemoFun を使って作ったフィボナッチ関数：

以下の内容のmemoFib.smlを用意

   fun fib 0 = 1
     | fib 1 = 1
     | fib n = fib (n - 1) + fib (n - 2)
   fun makeMemoFun f =
       let exception NotThere
           val memo = ref (fn x => (raise NotThere))
       in fn x => !memo x
             handle NotThere =>
                   let val v = f x
                       val oldMemo = !memo
                   in (memo := (fn y => if x = y then v else oldMemo y);
                       v)
                   end
       end
   val memoFib = makeMemoFun fib
   val _ = memoFib 43

2.
以下の内容のmemoFib.smiを用意
```
   _require "basis.smi"
```

コンパイルし実行。

   $ smlsharp -o memoFib memoFib.sml
   $ time memoFib
   real    0m3.380s
   user    0m3.380s
   sys     0m0.000s

fasetFib関数：

以下の内容のfastFib.smlを用意

   local
      exception NotThere
      fun f memo 0  = 1
        | f memo 1  = 1
        | f memo n =
            !memo n
              handle NotThere =>
                     let val v = f memo (n - 1) + f memo (n - 2)
                         val oldMemo = !memo
                         val _ = memo := (fn y => if n = y then v else oldMemo y)
                     in v
                     end
   in val fastFib = f (ref  (fn x => raise NotThere))
   end

   val _ = fastFib 43

2.
以下の内容のfastFib.smiを用意
```
   _require "basis.smi"
```

コンパイルし実行。

   $ smlsharp -o fastFib fastFib.sml
   $ time fastFib
   real    0m0.002s
   user    0m0.000s
   sys     0m0.000s

以上の通り、fastFibの方が圧倒的に速いことが確認できる。