From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id F29ADBC6B for ; Wed, 27 Jun 2007 18:53:29 +0200 (CEST) Received: from mail17.bluewin.ch (mail17.bluewin.ch [195.186.18.64]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l5RGrTlT006396 for ; Wed, 27 Jun 2007 18:53:29 +0200 Received: from [10.0.1.2] (85.2.100.178) by mail17.bluewin.ch (Bluewin 7.3.121) id 467A5C24001BA29C for caml-list@yquem.inria.fr; Wed, 27 Jun 2007 16:53:29 +0000 Mime-Version: 1.0 (Apple Message framework v752.2) In-Reply-To: <200706271453.06045.jon@ffconsultancy.com> References: <200706271314.35134.jon@ffconsultancy.com> <1A1D6F56-B3DB-4552-969C-9859482175AC@lrde.epita.fr> <200706271453.06045.jon@ffconsultancy.com> Content-Type: text/plain; charset=ISO-8859-1; delsp=yes; format=flowed Message-Id: <775B32CD-2A00-4FB8-842A-914A83FB8466@epfl.ch> Content-Transfer-Encoding: quoted-printable From: =?ISO-8859-1?Q?Daniel_B=FCnzli?= Subject: Hash-consing (was Re: [Caml-list] The Implicit Accumulator: a design pattern using optional arguments) Date: Wed, 27 Jun 2007 18:53:54 +0200 To: caml-list@yquem.inria.fr X-Mailer: Apple Mail (2.752.2) X-Miltered: at discorde with ID 46829609.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; bunzli:01 buenzli:01 hash-consing:01 memoize:01 hashtbl:01 hashtbl:01 val:01 hash-consing:01 structurally:01 structurally:01 filliatre:01 type-safe:01 modular:01 lri:01 filliatr:01 Le 27 juin 07 =E0 15:53, Jon Harrop a =E9crit : > Basically, you memoize strings: > > # let symbol =3D > let m =3D Hashtbl.create 1 in > fun string -> > try Hashtbl.find m string with Not_found -> > Hashtbl.add m string string; > string;; > val symbol : '_a -> '_a =3D It should be pointed out that this trick, known as hash-consing, is =20 not limited to strings. Basically for a given type you create a =20 single value representing all values that are structurally =20 equivalent. It allows to compare values structurally by using =20 physical equality. This paper [1] shows how to abstract the design =20 pattern. Daniel [1] Jean-Christophe Filli=E2tre, Sylvain Conchon, Type-safe modular hash-=20 consing, Proceedings of the 2006 workshop on ML. http://www.lri.fr/~filliatr/ftp/publis/hash-consing2.ps.gz