(********************************************************************)
(*  OCaml code from the book ``Learn Programming with OCaml''       *)
(*  See https://usr.lmf.cnrs.fr/lpo/                                *)
(*                                                                  *)
(*  Sylvain Conchon and Jean-Christophe Filliâtre                   *)
(*  Copyright 2025 Université Paris-Saclay and CNRS                 *)
(*                                                                  *)
(*  Openly licensed via CC BY SA 4.0                                *)
(*  See https://creativecommons.org/licenses/by-sa/4.0/deed.en      *)
(********************************************************************)

(* Program 87 on page 370
   Hash-consing (code) *)

  type tree = E | N of int * tree * char * tree

  let empty =
    E

  let unique = function
    | E -> 0
    | N (u, _, _, _) -> u

  module X = struct
    type t = tree
    let hash = function
      | E ->
          0
      | N (_, l, c, r) ->
          (19 * (19 * unique l + Char.code c) + unique r)
          land max_int
    let equal t1 t2 = match t1, t2 with
      | E, E -> true
      | N (_, l1, c1, r1), N (_, l2, c2, r2) ->
          l1 == l2 && c1 == c2 && r1 == r2
      | _ -> false
  end
  module W = Weak.Make(X)
  let nodes = W.create 5003

  let node =
    let cpt = ref 1 in
    fun l c r ->
      let n0 = N (!cpt, l, c, r) in
      let n = W.merge nodes n0 in
      if n == n0 then incr cpt;
      n

This document was generated using caml2html