From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA30139; Mon, 2 Aug 2004 13:18:43 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA30582 for ; Mon, 2 Aug 2004 13:18:42 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i72BIfSH008970 for ; Mon, 2 Aug 2004 13:18:41 +0200 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id i72BIYU0076368 ; Mon, 2 Aug 2004 13:18:34 +0200 (CEST) X-Ids: 165 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id JAA62160 ; Mon, 2 Aug 2004 09:46:33 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id JAA454888 ; Mon, 2 Aug 2004 09:45:54 +0200 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Mon, 2 Aug 2004 09:45:54 +0200 (DST) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: Jon Harrop cc: caml-list@inria.fr Subject: Re: [Caml-list] Functional arrays In-Reply-To: <200407311823.40820.jon@jdh30.plus.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 410E2311.002 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 410E230A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; pons:01 pons:01 etu:99 caml-list:01 splay:01 thesis:01 persistency:01 memoizing:01 baire:01 isomorphism:01 amortized:01 okasaki:01 okasaki's:01 haskell:01 okasaki's:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, > > > Incidentally, does anyone have a functional array implementation As far as I know there are 3 main techniques to implement functional arrays : - version arrays - maps with indexed access - random acces lists A version array is a classical array (O(1) acces) where persistance is handled by 'indirection' and 'cache' : a pointer based mechanism allows you to restore the complete history of the array by writing back when needed this information in the main array. classical examples : - an array of stamped lists (confer to the ML version of Martin Erwing's functional graph library) - an array of trees (confer to the work of Melissa O'Neill where the underlying trees are splay trees - she has written a Master Thesis, a JFP paper and part of her doctoral dissetation on the subject) The other two techniques handle persistency by copying and sharing (as usual in functional programming). - The map family is just a classical tree-like data structure optimized for fast index location (the n-th element). Usually, the balanced scheme used is Stephen Adam's weight-balanced trees because memoizing in every node the size of the subtree allows a fast index computation (see Baire, /set folder) - The random acces list family is based on the isomorphism of binary numbers and a list of increasing 2^k sized trees. There are many well known data structures that can be seen as a particular case of this scheme including binomial heaps (Vuillemin) and their amortized variants (Okasaki-Brodal), and functional arrays (Okasaki) You will find functional arrays code in - Edison (Okasaki's Haskell data structure library) - Markus Mottl port of Okasaki's book - Baire > Well, by "array" I mean a container with O(1) random access where > "n" is the number of elements already in the container. - version array O(1) access to the current array / up to O(n) for previous versions - maps O(log n) access to all arrays - ral O(log n) access to all arrays Diego Olivier ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners