Re: hashtables for mutable records

[Pierre Weis <Pierre.Weis@inria.fr>]

>     Hello,
> 
> I want to do an hashtable on mutable and polymorphic records. Standard
> module Hashtbl is not suitable because:
>   - Hashtbl.HashType doesn't accept polymorphic types.
>   - Hashtbl.hash is susceptible to setups of a mutable fields.
> 
> I would appreciate any suggestion.
> 
>   Cheers,
> 
>        Yann Coscoy

You can use a unique integer field into your records to get a suitable
hash key (not sensible to mutation of your records). Of course you
must use your own hashing function that just reads this fixed integer
field.

As of polymorphism, if your problem is just to have keys or values
belonging to a parameterized data type, you can directly use the
creation and manipulation functions from the Hashtbl module
(Hashtbl.create, Hashtbl.add, etc): they accept to manipulate
polymorphic tables. Since usage of these functions with a user defined
hash function is not available from the Hashtbl module, you should
rewrite some parts of its code into your own hash table module.

If your polymorphism problem is deeper, namely you want to create a
polymorphic hash table, there is not very much to do for you, since
hash tables being mutable structures, type constraints must be
cumulative: for example, if you define tab as an (int, 'a list)
Hashtbl.t then adding a string list into tab will constraint the type
of tab to be (int, string list) Hashtbl.t; hence, after adding a
string list into tab, you are forced to add string list into it and
you cannot add an int list into it. This is simple to explain: if
there are objects of various (uncompatible) types into the table, how
can we guess the type of something we get from the table ?

Note that you can define a concrete sum type to solve this problem, if
the types of objects you want to store in the table are statically
known; for instance for int list and bool list you can define:

type storable =
   | IL of int list
   | SL of string list

and then use an (int, storable) Hashtbl.t.
Admitedly, this trick is inefficient if you really need polymorphism,
but in some cases it is really useful.

Hope your problem is the simple one!

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/