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.3 required=5.0 tests=AWL,HTML_MESSAGE autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 23677BDC1 for ; Fri, 20 Jul 2007 09:55:36 +0200 (CEST) Received: from wr-out-0506.google.com (wr-out-0506.google.com [64.233.184.224]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6JHDiZF025204 for ; Thu, 19 Jul 2007 19:13:46 +0200 Received: by wr-out-0506.google.com with SMTP id i21so534431wra for ; Thu, 19 Jul 2007 10:13:44 -0700 (PDT) Received: by 10.142.77.11 with SMTP id z11mr216835wfa.1184865222504; Thu, 19 Jul 2007 10:13:42 -0700 (PDT) Received: by 10.142.72.4 with HTTP; Thu, 19 Jul 2007 10:13:42 -0700 (PDT) Message-ID: <28fa90930707191013y11fa73abx617c5b813e72b646@mail.gmail.com> Date: Thu, 19 Jul 2007 10:13:42 -0700 From: "Luca de Alfaro" To: "Hugo Ferreira" Subject: Re: [Caml-list] Vec: a functional implementation of extensible arrays Cc: "Loup Vaillant" , caml-list@yquem.inria.fr In-Reply-To: <469F1E32.3040502@inescporto.pt> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_91668_27897791.1184865222473" References: <28fa90930707181032q7681340pc30fb47434aff5fc@mail.gmail.com> <6f9f8f4a0707190045g609abca4kfa3bb39d93604081@mail.gmail.com> <469F1E32.3040502@inescporto.pt> X-Miltered: at concorde with ID 469F9BC8.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; arrays:01 nonstandard:01 filliatre:01 arrays:01 backtracking:01 nodes:01 backtracking:01 lri:01 filliatr:01 publis:01 ocaml:01 iterating:01 bounded:01 worst-case:01 amortized:01 ------=_Part_91668_27897791.1184865222473 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Reading the paper, I noticed that my name "put" for assigning a value to a position is highly nonstandard. I have changed it to "set" for version 1.1 of Vec. Hopefully, changing so soon will avoid confusion... sorry. Luca On 7/19/07, Hugo Ferreira wrote: > > Hello, > > For those of you interested in functional array consider Sylvain Conchon > and Jean-Christophe Filli=E2tre paper in [1]. The Union-Find (UF) uses > persistent arrays as its base data structure. I have made tests with the > UF using the code provided, an implementation of k-BUF data structure > (delayed backtracking) and altered version of the persistent array (fat > nodes + delayed backtracking). The tests I did show that this version of > persistent arrays is very efficient (especially for single threaded > backtracking). > > Maybe Luca could pit his implementation against that of the article and > report on how they fare? > > Regards, > Hugo Ferreira. > > [1] http://www.lri.fr/~filliatr/ftp/publis/puf-wml07.ps > > Loup Vaillant wrote: > > 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 > > > > _______________________________________________ > > Caml-list mailing list. Subscription management: > > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > > Archives: http://caml.inria.fr > > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > > Bug reports: http://caml.inria.fr/bin/caml-bugs > > > > _______________________________________________ > Caml-list mailing list. Subscription management: > http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list > Archives: http://caml.inria.fr > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > Bug reports: http://caml.inria.fr/bin/caml-bugs > ------=_Part_91668_27897791.1184865222473 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Reading the paper, I noticed that my name "put" for assigning a v= alue to a position is highly nonstandard.
I have changed it to "se= t" for version 1.1 of Vec.  Hopefully, changing so soon will avoi= d confusion... sorry.=20

Luca

On 7/19/07, Hugo Ferreira <hmf@inescporto.pt> wrote:
Hello,

For those of you interested in functional array consider Sylv= ain Conchon
and Jean-Christophe Filli=E2tre paper in [1]. The Union-Find= (UF) uses
persistent arrays as its base data structure. I have made tes= ts with the
UF using the code provided, an implementation of k-BUF data structure(delayed backtracking) and altered version of the persistent array (fatnodes + delayed backtracking). The tests I did show that this version of
persistent arrays is very efficient (especially for single threaded
= backtracking).

Maybe Luca could pit his implementation against that = of the article and
report on how they fare?

Regards,
Hugo Ferr= eira.

[1] http://www.lri.fr/~filliatr/ftp/publis/puf-wml07.ps

Loup Vailla= nt wrote:
> 2007/7/18, Luca de Alfaro < luca@dealfaro.org>:
>> Dear All,
>>
>> I = would like to share with you an Ocaml implementation of extensible
>&= gt; arrays.
>>  The implementation is functional, based = on balanced trees (and on the
>> code
>> for Set and Map); I called the module Vec (fo= r vector - I like
>> short names).  You can find it at>> http://www.dea= lfaro.com/home/vec.html
>> Module Vec provides, in log-time:
>>
>>&= nbsp; Access and modification to arbitrary elements ( Vec.put n el v p= uts
>> element
>> el in position n of vector v, for insta= nce).
>> Concatenation
>> Insertion and removal of elements from a= rbitrary positions
>> (auto-enlarging
>> and auto-shrinki= ng 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 ca= n cause stack overflows.
>>
>> I have been using this dat= a structure for some months, and it has been
>> very
>> h= andy in a large number of occasions.  I hope it can be as useful = to you.
>>
>> I would appreciate all advice and feedback. &= nbsp;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 definiti= on, 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
>
> ___________________= ____________________________
> Caml-list mailing list. Subscription m= anagement:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Arc= hives: http://caml.inria.fr
> Be= ginner's list:=20 http://groups.yah= oo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
_______________________________________________
Caml-list mailing li= st. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/ca= ml-list
Archives: http://caml.inria.fr=
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: <= a href=3D"http://caml.inria.fr/bin/caml-bugs"> http://caml.inria.fr/bin/caml-bugs

------=_Part_91668_27897791.1184865222473--