Re: [Caml-list] Help with simple ocaml memoization problem

["Jean-Christophe Filliâtre" <Jean-Christophe.Filliatre@lri.fr>]

Evan Klitzke wrote:
> One question that I have is what is the difference
> between the Map and Hashtbl modules? From the documentation they look
> very similar -- why did you use Hashtbl here rather than Map?

Hashtbl implements an imperative data structure i.e. association tables
which are modified in-place when inserting, removing, etc.

On the contrary, Map implements a persistent data structure i.e. tables
which are not modified when you perform operations; instead, new tables
are returned, the previous ones being unchanged.

(This can be seen in the types

	Hashtbl.add : ('a, 'b) Hashtbl.t -> 'a -> 'b -> unit
	SomeMap.add : key -> 'a -> 'a t -> 'a t

Here you can see the return type unit for hash tables, and the return
type 'a t for the maps.)

There are many cases where persistence can help improving your code:
backtracking, sharing between several data structures, clarity and
correctness of the code, etc.

In the case of this particular example, however, the use of a hash table
is perfectly fine, as demonstrated by Peng. With a good hash function,
insertion in a hash table typically runs in constant time, while
insertion in a map has logarithmic cost. But don't be misleaded by this
performance comparison: persistence has so many advantages that it is
often the case that you want to pay this extra cost.

-- 
Jean-Christophe Filliâtre
http://www.lri.fr/~filliatr/