Q: hashtables of parametrized types in Ocaml?

Q: hashtables of parametrized types in Ocaml?

[Basile STARYNKEVITCH]

Hello

[[English]]

Suppose I have

    (* a symbol has a name and a value; value type is unspecified
       here; in practice it will be defined in another module! *)
    type 'a asymbol_t = { sy_name: string; sy_val: 'a }

    (* the hash of a symbol is the hash of its name *)
    let symhash { sy_name= name } = Hash.hash name;

Now I would like to define hashtable of symbol thru the Hashtbl.Make
functor.

I tried 

    module SymbolHashtbl =
      Hashtbl.Make(struct
	type t = 'a asymbol_t
	let equal = (==)
	let hash = symhash
      end)

but it doesn't work! How can I achieve an equivalent result? Of course
I would like the resulting symbol hashtable module to have a key type
parametrized by 'a (symbols' value type) and a table type parametrized
by 'a (the same symbols' value type) and by 'b (the arbitrary hash
value type - noted 'a on section 16.10 page 186 of refman1.05)

The reason of all this is that I have in my application (some kind of
translator, building and working on program abstract syntax trees)
symbols and tree nodes - each node has a symbol and may have
subnodes. A symbol may have as value a tree node.  So I have a module
Symbol (defining type 'a asymbol_t) and another module Abstree (for
abstract syntax trees) defining type node_t and symbol_t = node_t
asymbol_t.

Perhaps a double functor is the answer, but I can't figure it out!

[[French summary]]

Comment créer une table de hash (via Hashtbl) de types parametrés. Mon
type asymbol_t (defini ci-dessus) est parametré par le type 'a des
valeurs de symbole (instantié dans un autre module). Mais le hashage
ne porte que sur le nom du symbole. Comment faire une table de hash
sur ces symboles.  


N.B. Any opinions expressed here are solely mine, and not of my organization.
N.B. Les opinions exprimees ici me sont personnelles et n engagent pas le CEA.


----------------------------------------------------------------------
Basile STARYNKEVITCH   ----  Commissariat à l Energie Atomique 
DRN/DMT/SERMA * CEA/Saclay bat.470 * 91191 GIF/YVETTE CEDEX * France
fax: (33) 01,69.08.85.68; phone: 01,69.08.40.66; home: 01,46.65.45.53
email: Basile . Starynkevitch @ cea . fr  (but remove white space)
I speak french, english, russian. Je parle français, anglais, russe.
----------------------------------------------------------------------

Re: Q: hashtables of parametrized types in Ocaml?

[Mark Hayden]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2871 bytes --]


Here is a similar example that works for me.
This is for hash tables that use MD5 digest 
strings for keys.

--Mark


.mli:

  module MD5_handler : ( Handler.S with type key = Digest.t )

.ml:

  module MD5_key =
    struct
      type t = Digest.t
      let equal = (=)
      let hash s = abs (Hsys.pop_int s 0)
    end

  module MD5_hashtbl = Hashtbl.Make ( MD5_key )

pop_int is a function thats reads an integer in a string:

  val pop_int : string -> int -> int


>
>Hello
>
>[[English]]
>
>Suppose I have
>
>    (* a symbol has a name and a value; value type is unspecified
>       here; in practice it will be defined in another module! *)
>    type 'a asymbol_t = { sy_name: string; sy_val: 'a }
>
>    (* the hash of a symbol is the hash of its name *)
>    let symhash { sy_name= name } = Hash.hash name;
>
>Now I would like to define hashtable of symbol thru the Hashtbl.Make
>functor.
>
>I tried 
>
>    module SymbolHashtbl =
>      Hashtbl.Make(struct
>	type t = 'a asymbol_t
>	let equal = (==)
>	let hash = symhash
>      end)
>
>but it doesn't work! How can I achieve an equivalent result? Of course
>I would like the resulting symbol hashtable module to have a key type
>parametrized by 'a (symbols' value type) and a table type parametrized
>by 'a (the same symbols' value type) and by 'b (the arbitrary hash
>value type - noted 'a on section 16.10 page 186 of refman1.05)
>
>The reason of all this is that I have in my application (some kind of
>translator, building and working on program abstract syntax trees)
>symbols and tree nodes - each node has a symbol and may have
>subnodes. A symbol may have as value a tree node.  So I have a module
>Symbol (defining type 'a asymbol_t) and another module Abstree (for
>abstract syntax trees) defining type node_t and symbol_t = node_t
>asymbol_t.
>
>Perhaps a double functor is the answer, but I can't figure it out!
>
>[[French summary]]
>
>Comment créer une table de hash (via Hashtbl) de types parametrés. Mon
>type asymbol_t (defini ci-dessus) est parametré par le type 'a des
>valeurs de symbole (instantié dans un autre module). Mais le hashage
>ne porte que sur le nom du symbole. Comment faire une table de hash
>sur ces symboles.  
>
>
>N.B. Any opinions expressed here are solely mine, and not of my organization.
>N.B. Les opinions exprimees ici me sont personnelles et n engagent pas le CEA.
>
>
>----------------------------------------------------------------------
>Basile STARYNKEVITCH   ----  Commissariat à l Energie Atomique 
>DRN/DMT/SERMA * CEA/Saclay bat.470 * 91191 GIF/YVETTE CEDEX * France
>fax: (33) 01,69.08.85.68; phone: 01,69.08.40.66; home: 01,46.65.45.53
>email: Basile . Starynkevitch @ cea . fr  (but remove white space)
>I speak french, english, russian. Je parle français, anglais, russe.
>----------------------------------------------------------------------
>
>
>

Re: Q: hashtables of parametrized types in Ocaml?

[Christian Boos]

Mark Hayden writes:
 > 
 > Here is a similar example that works for me.
 > This is for hash tables that use MD5 digest 
 > strings for keys.
 > 
 > --Mark
 > <<.mli and .ml snipped>>

	Hello, 

  I don't think this was an example similar to the original post. 
What Basile needed was a parametrized type for the key type:

He wrote:
 > >I tried 
 > >
 > >    module SymbolHashtbl =
 > >      Hashtbl.Make(struct
 > >	type t = 'a asymbol_t
 > >	let equal = (==)
 > >	let hash = symhash
 > >      end)
 > >
 > >but it doesn't work! How can I achieve an equivalent result? Of course
 > > <<...>>
 > >Perhaps a double functor is the answer, but I can't figure it out!

I think his idea of a "double functor" is the good one.


Try:

    module MakeHashtbl (S : sig type v end) =
      Hashtbl.Make 
        (struct
          type t = S.v asymbol_t
          let equal = (==)
          let hash = symhash
        end)


and then later:

    module NodeSymbolHashtbl = MakeHashtbl (sig type v = node_t end)


-- Christian