Re: [Ocaml-lib-devel] Suggestion for a new module

[Martin J. <mar...@em...>]

On Thu, 5 May 2005, Alain Frisch wrote:

> Dear Ext-lib developers,
>
> This tiny module:
> http://www.eleves.ens.fr/home/frisch/soft.html#memo
>
> implements memoization tables with bounded size. Such a table can be
> used to memoize a function without using a lot of memory. A hash
> function is used to retrieve a previously computed value for a given
> key. The implementation uses a nice and simple heuristic to choose what
> to do in case of collision on the hash value for two keys.
>
> Feel free to add this module to ext-lib if you think it can be useful.

On a related topic: the Hashtbl module
Would it be a good thing to add functions which do not require to
recompute the hashed key (with Hashtbl.hash), for efficiency purposes:

val unsafe_find : ('key, 'data) t -> int -> 'key -> 'data
val unsafe_mem : ('key, 'data) t -> int -> 'key -> bool
val unsafe_add : ('key, 'data) t -> int -> 'key -> 'data -> unit
...

For instance, we could write:

let get tbl key lazy_data =
  let h = Hashtbl.hash key in
  try Hashtbl.unsafe_find tbl h key
  with Not_found ->
     let data = Lazy.force lazy_data in
     Hashtbl.unsafe_add tbl h key data;
     data

Martin

--
Martin Jambon, PhD
http://martin.jambon.free.fr