Hash-consing (was Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments)

["Daniel Bünzli" <daniel.buenzli@epfl.ch>]

Le 27 juin 07 à 15:53, Jon Harrop a écrit :

> Basically, you memoize strings:
>
> # let symbol =
>     let m = Hashtbl.create 1 in
>     fun string ->
>       try Hashtbl.find m string with Not_found ->
>       Hashtbl.add m string string;
>       string;;
> val symbol : '_a -> '_a = <fun>

It should be pointed out that this trick, known as hash-consing, is  
not limited to strings. Basically for a given type you create a  
single value representing all values that are structurally  
equivalent. It allows to compare values structurally by using  
physical equality. This paper [1] shows how to abstract the design  
pattern.

Daniel

[1]

Jean-Christophe Filliâtre, Sylvain Conchon, Type-safe modular hash- 
consing, Proceedings of the 2006 workshop on ML.
http://www.lri.fr/~filliatr/ftp/publis/hash-consing2.ps.gz