Hashed fixpoint function, an example of parameterizing the algorithm by equality and hashing functions without exposing it as a functor, and still using the functorial interface of Hashtbl.

fixpoint.ml

(** Packs typed values into boxes preserving equality and hashing. *)
module type HASHED =
sig
  type t
  val hash  : t -> int
  val equal : t -> t -> bool
  val pack  : ('a -> int) -> ('a -> 'a -> bool) -> 'a -> t
end

module Hashed : HASHED =
struct
  type t = {
    hash  : int;
    value : Obj.t;
    equal : Obj.t -> Obj.t -> bool
  }

  let hash x = x.hash

  let equal x y =
    x.hash = y.hash && x.equal x.value y.value

  let pack h eq x =
    let eq a b = eq (Obj.obj a) (Obj.obj b) in
    {hash=h x; value=Obj.repr x; equal=eq}
end

module Table = Hashtbl.Make(Hashed)

(** Fixpoint with memoization. *)
let rec fix_hashed equal hash f =
  let table   = Table.create 7 in
  let pack x  = Hashed.pack hash equal x in
  let rec g x =
    let key = pack x in
    try Table.find table key with
	Not_found ->
	  let y = f g x in
	  Table.add table key y;
	  y in
  g