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 TAA20407; Sat, 31 Jul 2004 19:26:39 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA19520 for ; Sat, 31 Jul 2004 19:26:38 +0200 (MET DST) Received: from ptb-relay02.plus.net (ptb-relay02.plus.net [212.159.14.213]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i6VHQbEV002293 for ; Sat, 31 Jul 2004 19:26:37 +0200 Received: from [80.229.56.224] (helo=chetara) by ptb-relay02.plus.net with esmtp (Exim) id 1Bqxcz-0005GQ-D5 for caml-list@inria.fr; Sat, 31 Jul 2004 17:26:37 +0000 From: Jon Harrop To: Subject: [Caml-list] Functional arrays Date: Sat, 31 Jul 2004 18:23:40 +0100 User-Agent: KMail/1.6.2 References: <410B5EBD.6060800@cgorski.org> <200407311444.56864.jon@jdh30.plus.com> <1091291731.11540.368.camel@pelican.wigram> In-Reply-To: <1091291731.11540.368.camel@pelican.wigram> MIME-Version: 1.0 Content-Disposition: inline Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200407311823.40820.jon@jdh30.plus.com> X-Miltered: at nez-perce with ID 410BD64D.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; 2004:99 2004:99 44,:01 lazily:01 arrays:01 arrays:01 complexity:02 binary:02 tree:02 enforce:02 enforce:02 wrote:03 wrote:03 array:04 array:04 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Saturday 31 July 2004 17:35, skaller wrote: > On Sat, 2004-07-31 at 23:44, Jon Harrop wrote: > > Incidentally, does anyone have a functional array implementation (which > > doesn't suck ;-)? > > Map? Well, by "array" I mean a container with O(1) random access where "n" is the number of elements already in the container. ;-) Also, I'd like it to "enforce" its size. With a map you could have an element missing. Although you may be able to write a balanced binary tree which used its depth information to enforce each element being filled. That might be interesting... Anyway, I'm considering implementing arrays which look functional but which use built-in arrays and keep track of "derived" arrays (e.g. subarrays) using mutables under the bonnet and lazily re-jig them. I think this could make things substantially faster (better asymptotic complexity) in my context but I'm entirely unsure of how bad the constant prefactor would be hit. Cheers, Jon. ------------------- 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