Fix.HashCons
This module 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.
val id : 'data cell -> int
id cell
returns the integer identifier of the cell cell
.
val data : 'data cell -> 'data
data cell
returns the payload of the cell cell
.
Cells come with an equality test equal
, a comparison function compare
, and and a hash function hash
. These functions exploit the cell's unique identifier only: the data is ignored.
As a result, 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
.
equal
determines whether two cells are the same cell. It is based on the cells' integer identifiers.
compare
implements a total order on cells, It is based on the cells' integer identifiers.
val hash : 'data cell -> int
hash
is a hash function on cells. It is based on the cells' integer identifiers.
module type SERVICE = sig ... end
A 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.
The functor Make
expects a type data
for which a memoizer exists, and produces a hash-consing service for it.
module ForHashedType (T : sig ... end) : SERVICE with type data = T.t
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 ForHashedTypeWeak (T : sig ... end) : SERVICE with type data = T.t
ForHashedTypeWeak
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.