Version franaise
Home About Download Resources Contact us
Browse thread
The Implicit Accumulator: a design pattern using optional arguments
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Daniel_Bnzli <daniel.buenzli@e...>
Subject: Hash-consing (was Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments)
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 Fillitre, 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