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.7 required=5.0 tests=AWL,SPF_NEUTRAL autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id D931ABC69 for ; Mon, 30 Jul 2007 13:51:31 +0200 (CEST) Received: from ctsmtpout2.frontal.correo (smtp.telefonica.net [213.4.149.66]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6UBpVxB011485 for ; Mon, 30 Jul 2007 13:51:31 +0200 Received: from tux-chan (88.6.6.94) by ctsmtpout2.frontal.correo (7.2.056.6) (authenticated as ferferse$telefonica.net) id 46ACE9550001C8ED for caml-list@inria.fr; Mon, 30 Jul 2007 13:51:31 +0200 Received: from batsman by tux-chan with local (Exim 3.36 #1 (Debian)) id 1IFTmc-0006CO-00 for ; Mon, 30 Jul 2007 13:51:30 +0200 Date: Mon, 30 Jul 2007 13:51:29 +0200 From: Mauricio Fernandez To: caml-list@inria.fr Subject: Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append. Message-ID: <20070730115129.GD28879@tux-chan> Mail-Followup-To: caml-list@inria.fr References: <20070728233305.GB28879@tux-chan> <200707300146.20940.jon@ffconsultancy.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200707300146.20940.jon@ffconsultancy.com> User-Agent: Mutt/1.5.11 Sender: =?iso-8859-1?Q?Mauricio_Julio_Fern=E1ndez_Pradier?= X-Miltered: at discorde with ID 46ADD0C3.001 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; vectors:01 prepend:01 0100,:01 mutation:01 mutation:01 node:01 nodes:01 bounded:01 hofs:01 iter:01 iteri:01 wrote:01 wrote:01 extensible:01 experimental:01 On Mon, Jul 30, 2007 at 01:46:20AM +0100, Jon Harrop wrote: > On Sunday 29 July 2007 00:33:05 Mauricio Fernandez wrote: > > It is still young and experimental, but it's maybe worth a look. Any > > feedback is very welcome. > > Looks awesome! > > It seems to use mutation internally. Is it not thread safe? The structure is persistent and all operations are non-destructive. Mutation is used only in the rebalancing operation and in set, but they affect an ephemeral forest of ropes/vects and a new string/array respectively, so the original structure is never modified and in principle all operations should be thread-safe. Ropes/vects being functional doesn't mean that they will perform well in a persistent setting however, see the clarification at http://eigenclass.org/repos/oropes/head/doc/Vect.html > I have some suggestions: > > I'd like metadata in every node, so I can provide a constructor that combines > the metadata of child nodes and a cull function to accelerate searches. If I understand it correctly, that scheme could in the limit turn some O(n) searches into O(log n)?), right? Unlike Vec, Vect uses "compact" leaves (Leaf of 'a array) of bounded size (leaf_size, typically 16-64), which might not fit very well. Vect would need to know how to combine the metadata, wouldn't it? I was thinking about something like Leaf of ('meta -> 'meta -> 'meta) * 'meta * 'a array but I've realized that this wouldn't suffice. So, given that Vect.t is currently type 'a t = Empty | Concat of 'a t * int * 'a t * int * int | Leaf of 'a array something like this maybe? type ('a, 'meta) t = Empty of ('meta -> 'meta -> 'meta) | Concat of ('meta -> 'meta -> 'meta) * 'meta * ('a, 'meta) t * int * ('a, 'meta) t * int * int | Leaf of ('meta -> 'meta -> meta) * 'meta array * 'a array (* maybe also * 'meta to cache the last computation? *) or even without the ('meta -> 'meta -> 'meta) part, forcing the user to pass the function on each modification? Just thinking out loud. At any rate, it'd be better to provide it as a separate structure, any suggestions for the name?. > The usual HOFs, like map. I just pushed a patch with filter and map. The former is trivially implemented with fold + append (thanks to the O(1) append). I was going to code map the same way but I ended up making one that returns an isomorphic vect and is faster (since there's no need to rebalance). So Vect currently has iter, iteri, rangeiter, fold, map and filter. I'm considering renaming fold to fold_left and providing fold_right too. -- Mauricio Fernandez - http://eigenclass.org