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 79995BC70 for ; Fri, 10 Aug 2007 00:07:39 +0200 (CEST) Received: from py-out-1112.google.com (py-out-1112.google.com [64.233.166.178]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l79M7cTQ012375 for ; Fri, 10 Aug 2007 00:07:39 +0200 Received: by py-out-1112.google.com with SMTP id u52so1020698pyb for ; Thu, 09 Aug 2007 15:07:37 -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=qNB7/k1+ktnTrAJXo4+3p/kjQatmlPs5BW1n772vpmozEIZLAyTtjl2/lNYBxf3BjMK8TyIymbzzbDSz2C7k4nwVtSyA9aIZPMOm/JYfQ0b4U5627UCQIswv5Nr5Qg/dV07Q2mOJUYVaiLrQD2vfpExUeSBOd6JSQlDUZEbv1IE= 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=iZfn0G7PkryyiEqywx56rashf2dBzQy07LY/gZ7/1pEpRPt/Xtvs98bcMOHBpckm6b+V5pZxmYZCXCuXeqF9WY+ZyqHT92r5OlDR+Zdkb0noPF+VcGIx6sn8DilQy5bV+IMd866AIfz/dZaeAN6w1W/FT9p1it5ps3kL3KW/zzo= Received: by 10.142.222.21 with SMTP id u21mr521603wfg.1186697256865; Thu, 09 Aug 2007 15:07:36 -0700 (PDT) Received: by 10.142.80.9 with HTTP; Thu, 9 Aug 2007 15:07:36 -0700 (PDT) Message-ID: Date: Thu, 9 Aug 2007 15:07:36 -0700 From: "Nathaniel Gray" To: caml-list Subject: Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append. In-Reply-To: <20070728233305.GB28879@tux-chan> MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <20070728233305.GB28879@tux-chan> X-j-chkmail-Score: MSGID : 46BB902A.000 on discorde : j-chkmail score : X : 0/20 1 0.000 -> 1 X-Miltered: at discorde with ID 46BB902A.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; vectors:01 prepend:01 icfp:01 bounded:01 amortized:01 vectors:01 height:98 garbage:01 wrote:01 extensible:01 extensible:01 experimental:01 caml-list:01 strings:01 append:02 On 7/28/07, Mauricio Fernandez wrote: > In the aftermath of the ICFP contest, during which I used Luca de Alfaro's > Vec, I felt like implementing ropes, based on Boehm's paper and the well-known > code included in his conservative garbage collector. > > I later realized that the basic implementation strategies ("dense" leaves, > bounded tree height and amortized constant time concatenation of small > strings) could be generalized to build general extensible vectors similar to > Vec. > > ... > > You can find the code for both Rope and Vect at > http://eigenclass.org/repos/oropes/head/ > It is still young and experimental, but it's maybe worth a look. Any feedback > is very welcome. > > The documentation can be found under > http://eigenclass.org/repos/oropes/head/doc/ This looks pretty nice! I don't have an immediate need for it but it's a good thing to have in the toolbox. Thanks, -n8 -- >>>-- Nathaniel Gray -- Caltech Computer Science ------> >>>-- Mojave Project -- http://mojave.cs.caltech.edu -->