Re: [Caml-list] Vec: a functional implementation of extensible arrays

[Jon Harrop <jon@ffconsultancy.com>]

On Friday 20 July 2007 08:35:39 Loup Vaillant wrote:
> > ;-).  I am open to new ideas.  In part, I wanted a simple data structure
> > (easier to extend, among other things).  Also, I use Set, Map, etc, quite
> > often, and those are also balanced trees: I thought that if I can live
> > with those, I can probably live with Vec as well.

This is the beginnings of an awesome data structure!

> So can I. Your current implementation is already very attractive, and
> looks very usable. For the new idea, have you thought of making (or
> specifying) syntactic sugar to use your array?

Should be very easy using the new camlp4. You might like to add a slicing 
notation as well. :-)

> About improving performance...

I have two suggestions:

1. Add an extra node representing single elements that replaces Node(Empty, _, 
Empty). The reduces GC stress enormously and makes the whole thing ~30% 
faster.

2. Allow unbalanced sub trees. Balancing is slow and folds and maps don't need 
to rebalance, but "get" should force rebalancing. Extracting subarrays should 
return an unbalanced result.

> Is there a way to obtain a efficient filter?

Yes. I discovered a most-excellent way to do this. It requires arbitrary 
metadata in every node, a constructor that composes subnodes to create the 
metadata for the parent and a filter function that can cull branches from the 
search tree.

I used this in my Mathematica implementation to provide asymptotically fast 
filtering based upon lazily evaluated sets of symbols in each subnode. This 
gave huge performance improvements with no significant performance overhead.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists/?e