# 二分探索木を用いたテーブルの定義

```# module type TABLE =
sig
type ('a, 'b) t
val empty : ('a, 'b) t
val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
val retrieve : 'a -> ('a, 'b) t -> 'b option
val dump : ('a, 'b) t -> ('a * 'b) list
end;;
module type TABLE =
sig
type ('a, 'b) t
val empty : ('a, 'b) t
val add : 'a -> 'b -> ('a, 'b) t -> ('a, 'b) t
val retrieve : 'a -> ('a, 'b) t -> 'b option
val dump : ('a, 'b) t -> ('a * 'b) list
end
# module Table : TABLE =
struct
type ('a, 'b) t = Lf | Br of 'a * 'b * ('a, 'b) t * ('a, 'b) t

let empty = Lf

let rec add key datum = function
Lf -> Br (key, datum, Lf, Lf)
| Br (key', _, left, right) when key = key' ->
Br (key, datum, left, right)
| Br (key', datum', left, right) when key < key' ->
Br (key', datum', add key datum left, right)
| Br (key', datum', left, right) ->
Br (key', datum', left, add key datum right)

let rec retrieve key = function
Lf -> None
| Br (key', datum, _, _) when key = key' -> Some datum
| Br (key', datum, left, _) when key < key' ->
retrieve key left
| Br (key', datum, _, right) ->
retrieve key right

let rec dump = function
Lf -> []
| Br (key, datum, left, right) ->
(key, datum) :: dump left @ dump right
end;;
module Table : TABLE
```

```# let (<<<) table (key, content) = Table.add key content table;;
val ( <<< ) : ('a, 'b) Table.t -> 'a * 'b -> ('a, 'b) Table.t = <fun>
# let table = Table.empty
<<< (1, "hogehoge")
<<< (2, "fugafuga")
<<< (3, "hagehage");;
val table : (int, string) Table.t = <abstr>
# Table.retrieve 1 table;;
- : string option = Some "hogehoge"
# Table.retrieve 6 table;;
- : string option = None
# let table' = table <<< (1, "another one");;
val table' : (int, string) Table.t = <abstr>
# Table.retrieve 1 table';;
- : string option = Some "another one"
# Table.dump table;;
- : (int * string) list = [(1, "hogehoge"); (2, "fugafuga"); (3, "hagehage")]
```

モジュール化と実装の隠蔽はこのようにすればいいのですね。