Fix.HashConsSourceThis 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.
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.
hash is a hash function on cells. It is based on the cells' integer identifiers.
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.
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.
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.