Re: [Caml-list] Ropes and rope-like functional extensible vectors with O(1) prepend/append.

[Mauricio Fernandez <mfp@acm.org>]

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