第3回
課題4
平均（最悪でない）時間計算量がO(log n)であればいいので、例えば二分木を作ればいいはず。
二分木を作る場合、特に大変なのはremoveでしょうか。
1 module MyMultiset2 = functor (Elem : ORDERED_TYPE) -> struct
2 exception Error_btree
3 type t = Node of Elem.t * t * t | Leaf
4
5 (* 中略 *)
6
7 (* 木の最小要素を返す *)
8 let rec search_min set =
9 match set with
10 | Leaf -> raise Error_btree
11 | Node (x, Leaf, _) -> x
12 | Node (_, left, _) -> search_min left
13
14 (* 木の最小要素を消す *)
15 let rec delete_min set =
16 match set with
17 | Node (v, Leaf, right) -> right
18 | Node (v, left, right) -> Node (v, (delete_min left), right)
19 | Leaf -> raise Error_btree
20
21 (* 要素の削除 *)
22 let rec remove elem set =
23 match set with
24 | Leaf -> Leaf
25 | Node (v, left, right) when eq v elem ->
26 if (right = Leaf) then left
27 else if (left = Leaf) then right
28 else
29 let min = search_min right in
30 Node (min, left, delete_min right)
31 | Node (v, left, right) ->
32 if (grt elem v) then Node (v, left, remove elem right)
33 else Node (v, remove elem left, right)
34
35
36 (* 中略 *)
37 end
課題5
定義は自分で決めていいらしいので、「1000回addやremoveを繰り返しても、２つの実装の実行結果が変わらないこと」とか適当に定義すればいい思う。
真面目な解き方は誰かが加筆してくれることでしょう(ﾁﾗｯ
課題7
let recを使って
とすると、「Error: This expression has type 'a t -> 'b t but an expression was expected of type 'a -> 'b」と型エラーがでます。 そこでmodule recを駆使して書いてみると、
うまくいきます。詳しい解説はis2009のwikiに書かれています。
課題8
('a, 'b) equalは同値関係（=とか<=>）に対応する型だと思われます。（reflは反射律、symmは対称律、transは推移律に対応）
同値関係は「（AならばB）かつ（BならばA）」という命題と同じ（？）と考えられるので、('a, 'b) equalは、例えば
1 type ('a, 'b) equal = ('a -> 'b) * ('b -> 'a)
と定義すればいいと思います。
課題9
よく分かりません（
valueやexprの引数に('a, 'b) equalを持たせる理由が謎です。
なんとなく型キャストができるようにしなさいと言っているような気がしますが気のせいかもしれません。
だれか分かる人は加筆してください。