二分探索木を用いたテーブルの定義
# 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")]
モジュール化と実装の隠蔽はこのようにすればいいのですね。