0001017: Feature wish: hash consing

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0001017

OCaml

OCaml general

public

2002-03-18 22:18

2012-01-20 14:12

Reporter

administrator

Assigned To

Priority

normal

Severity

feature

Reproducibility

always

Status

resolved

Resolution

won't fix

Platform

OS Version

Product Version

Target Version

Fixed in Version

Summary

0001017: Feature wish: hash consing

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

Tags

No tags attached.

Attached Files

Relationships

Notes
(0006753) doligez (manager) 2012-01-20 14:12	We recommend using third-party libraries (e.g. Filliatre's hashcons library).

Issue History
Date Modified	Username	Field	Change
2005-11-18 10:13	administrator	New Issue
2012-01-20 14:12	doligez	Note Added: 0006753
2012-01-20 14:12	doligez	Status	acknowledged => resolved
2012-01-20 14:12	doligez	Resolution	open => won't fix
2012-01-20 14:12	doligez	Description Updated	View Revisions