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.9 required=5.0 tests=HTML_10_20,HTML_MESSAGE 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 59D9EBC69 for ; Wed, 18 Jul 2007 19:32:56 +0200 (CEST) Received: from wr-out-0506.google.com (wr-out-0506.google.com [64.233.184.230]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l6IHWrTp030401 for ; Wed, 18 Jul 2007 19:32:55 +0200 Received: by wr-out-0506.google.com with SMTP id i23so208495wra for ; Wed, 18 Jul 2007 10:32:52 -0700 (PDT) Received: by 10.143.38.6 with SMTP id q6mr59635wfj.1184779969684; Wed, 18 Jul 2007 10:32:49 -0700 (PDT) Received: by 10.142.72.4 with HTTP; Wed, 18 Jul 2007 10:32:49 -0700 (PDT) Message-ID: <28fa90930707181032q7681340pc30fb47434aff5fc@mail.gmail.com> Date: Wed, 18 Jul 2007 10:32:49 -0700 From: "Luca de Alfaro" To: caml-list@yquem.inria.fr Subject: Vec: a functional implementation of extensible arrays MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_79529_4284042.1184779969666" X-Miltered: at discorde with ID 469E4EC5.002 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; arrays:01 ocaml:01 arrays:01 iterating:01 stack:01 bounded:01 stack:01 ocaml:01 iterating:01 bounded:01 iterators:01 iterators:01 overflows:01 overflows:01 extensible:01 ------=_Part_79529_4284042.1184779969666 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline 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 http://www.dealfaro.com/home/vec.html 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, Luca ------=_Part_79529_4284042.1184779969666 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline 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 http://www.dealfaro.com/home/vec.html
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,

Luca


------=_Part_79529_4284042.1184779969666--