Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Vec: a functional implementation of extensible arrays
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2007-07-18 (17:32)
From: Luca de Alfaro <luca@d...>
Subject: Vec: a functional implementation of extensible arrays
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
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,