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=1.0 required=5.0 tests=AWL,SPF_NEUTRAL 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 C4FE3BC69 for ; Thu, 19 Jul 2007 09:45:49 +0200 (CEST) Received: from an-out-0708.google.com (an-out-0708.google.com [209.85.132.245]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6J7jmm5024008 for ; Thu, 19 Jul 2007 09:45:49 +0200 Received: by an-out-0708.google.com with SMTP id b15so119087ana for ; Thu, 19 Jul 2007 00:45:48 -0700 (PDT) DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=Gl5QUjezgGVYZbDg4Oh5/dJS6/1vUljMFjW9qfaKbq/LNyLrTR0MPgH2yhI+S5AA6targwUTUwhnYS/Dvo53GZ405RzCDNptdz39AIE4oi7scVS+m9ZGc1p+/hfiVFCls+8jPqMNG/OklVWHvkpbPqh4GGY9KPhPP2pjAYUGWSo= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:message-id:date:from:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=ES2Tku5Vqp6uNLftwsnr2OTL7mxiXkaA6g7sFg7tWsOvyCkIbCYzigURs91Uk3s0NCps2ftCTr2/W9WKOFTUsnbn9haoKLdNBzE40iO6E1wBh4yOMVShH5M39HAnyrB3gwzoF7weMSmz1IpVTyAxjsPUstTtTP/H5leGsiG8z4U= Received: by 10.100.10.20 with SMTP id 20mr759947anj.1184831148308; Thu, 19 Jul 2007 00:45:48 -0700 (PDT) Received: by 10.100.33.15 with HTTP; Thu, 19 Jul 2007 00:45:48 -0700 (PDT) Message-ID: <6f9f8f4a0707190045g609abca4kfa3bb39d93604081@mail.gmail.com> Date: Thu, 19 Jul 2007 09:45:48 +0200 From: "Loup Vaillant" To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Vec: a functional implementation of extensible arrays In-Reply-To: <28fa90930707181032q7681340pc30fb47434aff5fc@mail.gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <28fa90930707181032q7681340pc30fb47434aff5fc@mail.gmail.com> X-j-chkmail-Score: MSGID : 469F16AC.002 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at discorde with ID 469F16AC.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; arrays:01 ocaml:01 arrays:01 iterating:01 stack:01 bounded:01 stack:01 worst-case:01 amortized:01 uneasy:98 iterators:01 iterators:01 overflows:01 extensible:01 extensible:01 2007/7/18, Luca de Alfaro : > Dear All, > > I would like to share with you an Ocaml implementation of extensible arrays. > The implementation is functional, based on balanced trees (and on the code > for Set and Map); I called the module Vec (for vector - I like > short names). You can find it at > http://www.dealfaro.com/home/vec.html > Module Vec provides, in log-time: > > Access and modification to arbitrary elements ( Vec.put n el v puts element > el in position n of vector v, for instance). > Concatenation > Insertion and removal of elements from arbitrary positions (auto-enlarging > and auto-shrinking the vector). > as well as: > > All kind of iterators and some visitor functions. > Efficient translation to/from lists and arrays. > An advantage of Vec over List, for very large data structures, is that > iterating over a Vec of size n requires always stack depth bounded by log n: > with lists, non-tail-recursive functions can cause stack overflows. > > I have been using this data structure for some months, and it has been very > handy in a large number of occasions. I hope it can be as useful to you. > > I would appreciate all advice and feedback. Also, is there a repository > where I should upload it? Do you think it is worth it? > > All the best, > > Luca Very interesting. I always felt uneasy about the presence of imperative arrays without a functional counterpart. I can't wait to try it. Looking at your array type definition, I assume that the timings you specified are worst-case? Is it possible to achieve better (but amortized) bounds? Do you think it would be worth the trouble? I didn't see in your specs the complexity of your iterators. Does these work in linear time, like those of the List and Array module? Regards, Loup