Efficient hashconsing in OCaml

term.ml

type t = {
  mutable id: int; (* unique ID *)
  view: view;
}
and view =
  | Const of string
  | App of t * t

let equal t u = t.id = u.id
let hash t = Hashtbl.hash t.id

module H = Weak.Make(struct
    type nonrec t = t

    let equal (t1:t) (t2:t) : bool = match t1.view, t2.view with
      | Const s1, Const s2 -> s1=s2
      | App (x1,y1), App (x2,y2) -> equal x1 x2 && equal y1 y2
      | Const _, _
      | App _, _
        -> false

    let hash (t:t): int = match t.view with
      | Const s -> Hashtbl.hash (0, s)
      | App (t,u) -> Hashtbl.hash (1, hash t, hash u)
  end)

(* builds terms *)
let mk_ =
  let tbl = H.create 6000 in
  let n = ref 0 in
  fun (view:view): t ->
    let t = { id= -1; view; } in
    let u = H.merge tbl t in
    if t == u then (
      (* new term *)
      t.id <- !n;
      incr n;
    );
    u

let const x = mk_ (Const x)
let app x y = mk_ (App (x,y))

term.mli

type t = private {
  mutable id: int; (* unique ID *)
  view: view;
}
and view =
  | Const of string
  | App of t * t

val const : string -> t
val app : t -> t -> t