Re: hashtables for mutable records

From: Pierre Weis (Pierre.Weis@inria.fr)
Date: Thu Apr 27 2000 - 19:56:02 MET DST

  • Next message: Julian Assange: "Re: Objective Caml 3.00 released"

    > 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/



    This archive was generated by hypermail 2b29 : Thu Apr 27 2000 - 20:03:02 MET DST