hashtables for mutable records

hashtables for mutable records

[Coscoy, Yann]

    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

---------------------------------------------------------------------
Yann Coscoy
Informatique CDC - Direction des Techniques Avancées
4, rue Berthollet
94110 Arcueil
Tél. : 01 40 49 15 28
Fax. : 01 40 49 15 78
e-mail : Yann.Coscoy@icdc.caissedesdepots.fr

Re: hashtables for mutable records

[Pierre Weis]

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

Re: hashtables for mutable records

[Jacques Garrigue]

From: "Coscoy, Yann" <yann.coscoy@icdc.caissedesdepots.fr>

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

The standard functorial solution would be to define a new functor:

type 'a polyref = {mutable data: 'a; id: int}

module PolyHash(T : sig type t end) =
  Hashtbl.Make
    (struct
      type t = T.t polyref
      let equal a b = (a.id = b.id)
      let hash a = a.id
    end)

module IntHash = PolyHash(struct type t = int end)
module BoolHash = PolyHash(struct type t = bool end)

The only dificulty with such an approach is that you must use
different functions for different hashtables.
If you want to define new polymorphic functions using these
hashtables, you must again put them in a functor.

Regards,

Jacques
---------------------------------------------------------------------------
Jacques Garrigue      Kyoto University     garrigue at kurims.kyoto-u.ac.jp
		<A HREF=http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/>JG</A>

RE: hashtables for mutable records

[Coscoy, Yann]

  Hello,

Pierre Weis wrote :

> You can use a unique integer field into your records 

  It is the solution I use. But, I dislike it because it makes necessary to
embed the record in some abstract type. (You must hide the constructor of
the recors to guaranty the uniqueness of the integer.)

> Of course you must use your own hashing function that just reads this
fixed integer field.

  I can do that, but it make impossible to use Hashtbl.Make because of the
poymorphism of the record. 

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

I know I can solve my problem in this way. But I don't think that "cut,
paste, and patch the stdlib" is a good practice. So, I prefer to use the
integer itself as the key of hashtable and use the standard Hash module.

I partial solution would be to have another functor Make1 in module Hashtbl
with type 'a key. (It is just a partial solution, because it doesn't solve
the problem for type ('a, 'b) key and type ('a, 'b, 'c) key.)

 Yann coscoy

PS: the signature of this Make1 functor:

module type HashedType1 =
  sig
    type 'a t
    val equal: 'a t -> 'a t -> bool
    val hash: 'a t -> int
  end
  
module type S1 =
  sig
    type 'a key
    type ('a, 'b) t
    val create: int -> ('a, 'b) t
    val clear: ('a, 'b) t -> unit
    val add: ('a, 'b) t -> 'a key -> 'b -> unit
    val remove: ('a, 'b) t -> 'a key -> unit
  .....