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

# 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")]

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