HashCons offers support for setting up a hash-consed data type, that is, a data type whose values carry unique integer identifiers.
The type 'data cell describes a cell that carries a unique identifier id as well as a payload data.
This type is marked private, which means that the user has no direct way of allocating cells. Instead, the user must apply the functor Make (below) to obtain a function make which either allocates a fresh cell or returns an existing cell. The user is still allowed to read existing cells.
Accessors.
val id : 'data cell -> intval data : 'data cell -> 'dataCells come with an equality test, a comparison function, and and a hash function. These functions exploit the cell's unique identifier only -- the data is ignored.
Wherever a module of signature HashedType with type t = foo cell is expected, the module HashCons can be supplied. This holds regardless of the type foo.
val hash : 'data cell -> intA hash-consing service allocates uniquely-numbered cells for data. The smart constructor make either allocates a fresh cell or returns an existing cell, as appropriate.
module type SERVICE = sig ... endThe functor Make expects a type data for which a memoizer exists, and produces a hash-consing service for it.
ForHashedType is a special case of Make where it suffices to pass a hashed type T as an argument. A hash table is used to hold the memoization table.
module ForHashedType (T : Hashtbl.HashedType) : SERVICE with type data = T.tForHashedTypeWeak is a special case of Make where it suffices to pass a hashed type T as an argument. A weak hash table is used to hold the memoization table.
module ForHashedTypeWeak
(T : Hashtbl.HashedType) :
SERVICE with type data = T.t