blob: 90cf8931bbe63ee11806f39ca6dcf47236151d45 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
type ('a, _) order1 =
| Lt : ('a, 'b) order1
| Eq : ('a, 'a) order1
| Gt : ('a, 'b) order1
module type Type1 = sig
type 'a t
end
module type OrderedType1 = sig
include Type1
val compare : 'a t -> 'b t -> ('a, 'b) order1
end
module type S = sig
type 'a key
type 'a value
type t
val empty : t
val add : 'a key -> 'a value -> t -> t
val remove : 'a key -> t -> t
val find : 'a key -> t -> 'a value
end
module Make(Key : OrderedType1)(Value : Type1) :
(S with type 'a key = 'a Key.t and type 'a value = 'a Value.t) =
struct
type 'a key = 'a Key.t
type 'a value = 'a Value.t
type ex_key =
| Key : 'a key -> ex_key
type key_value_pair =
| KeyVal : 'a key * 'a value -> key_value_pair
module ExKey =
struct
type t = ex_key
let compare (Key k1) (Key k2) : int =
match Key.compare k1 k2 with
| Lt -> -1
| Eq -> 0
| Gt -> 1
end
module ExMap = Map.Make(ExKey)
type t = key_value_pair ExMap.t
let empty : t = ExMap.empty
let add (k: 'a key) (v: 'a value) (m: t) : t =
ExMap.add (Key k) (KeyVal (k, v)) m
let remove (k: 'a key) (m: t) : t =
ExMap.remove (Key k) m
let find (type a) (k: a key) (m: t) : a value =
let (KeyVal (kf, v)) = ExMap.find (Key k) m in
match Key.compare k kf with
| Eq -> v
| _ -> failwith "sth is wrong"
end
|
