Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Feature wish: hash consing #3266

Closed
vicuna opened this issue Mar 18, 2002 · 1 comment
Closed

Feature wish: hash consing #3266

vicuna opened this issue Mar 18, 2002 · 1 comment

Comments

@vicuna
Copy link

vicuna commented Mar 18, 2002

Original bug ID: 1017
Reporter: administrator
Status: closed (set by @xavierleroy on 2013-08-31T10:44:32Z)
Resolution: won't fix
Priority: normal
Severity: feature
Category: ~DO NOT USE (was: OCaml general)

Bug description

Bonjour,

les nouvelles weak hash table semblent idéales pour faire du hash-consing;
je pense qu'une implementation comme ci-dessous pourrait être un ajout
intéressant à la bibliothèque standard (il faudrait peut-être le rendre
thread-safe et detecter les débordements du compteur interne, enfin, il
y a de la marge).

-- Alain

module type HashConsType =
sig
type data
type t
val cons: data -> t
val data: t -> data

val compare: t -> t -> int
val hash: t -> int
val equal: t -> t -> bool
end

(* Implements Hashtbl.HashedType and Set.SortedType interfaces,
with all operations in O(1).

  • equal t1 t2 iff H.equal (data t1) (data t2)
  • compare and hash are compatible with equal
    *)

module HashCons(H : Hashtbl.HashedType) : HashConsType with type data = H.t =
struct
module Stamp = struct
type t = H.t * int
let equal (h1,) (h2,) = H.equal h1 h2
let hash (h,_) = H.hash h
end
module WH = Weak.Make(Stamp)
type data = H.t
type t = Stamp.t

let count = ref 0
let table = WH.create 5

let data (x,_) = x

(* Not thread safe ! *)
let cons x =
let c = (x,!count) in
let d = WH.merge table c in
if (c == d) then incr count;
d

let equal ((,i) : t) ((,j) : t) = i = j
let hash ((,i) : t) = i
let compare ((
,i) : t) ((_,j) : t) = compare i j
end

@vicuna
Copy link
Author

vicuna commented Jan 20, 2012

Comment author: @damiendoligez

We recommend using third-party libraries (e.g. Filliatre's hashcons library).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant