Re: [Caml-list] [RANT] String representation (was: Strings as arrays or lists...)

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

    Bonjour,

Some of the features you wish are 'not so hard to implement', at least
if you already have 'conceptually bugged low-level' strings :

> - Strings need fast concatenation and parts extraction, arrays do
> not need that.

Any 'fast mergeable' data structure will do it :

- trees of strings
- fast catenable lists

> - Arrays need fast random access by numeric index, strings do not
> need that.

You can easily hava a (log n/k + 1) acces where n is the total size of
the string and k is the size of each bucket (if you choose a data
structure with constant buffer size)

> - string is an abstract type, with fast concatenation (especially
> when one of the operands is not used anymore; this is like
> tail-recursion optimisation, but for strings);

You just have to free the unused buckets of you string. If you really
want tail recursive functions try a 'list' based data structure. That
seems to be what Alain Frisch did in CDuce.

> - there is also a `cursor' type, which is something like a pair
> (string, index in that string);

Easy... You can even do better : using a zipper you have constant
acces to the pointed element (instead of log n), with some bookkeeping
every time you move the index.

> - there are functions to move cursors forward and backward, take
>   substrings between two cursors, etc.;

Zippers only allow one (functional) pointer by data structure. For
this you will have to stick to an index with logarithmic time acces.
You can of course mix both (zippers + indexes)

> - there is a buffer type which is a byte array for low-level
> operations, and conversion functions between buffers and strings,
> with several possible encodings;

Yes... strings.


        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners