Re: [Ocaml-lib-devel] Xarray : resizeable arrays (first cut)

[Nicolas C. <war...@fr...>]

> A first cut at resizeable arrays.

Thanks Brian, we definitly need it in the ExtLib !

> - I haven't made the reallocation strategy explicit.  And I'm not sure I
> like the shrinking strategy.

The question is "when do you use shrinking ?". It seems that you're using
shrinking each time an element is removed, which is I think not the best way
of doing it. Typically, the life of an array looks like :
- add elements
- remove some eventually
- do some work with it (iter)
- loop

The user most of the time does not care at all if it's array is taking a
little too much memory, but some users in some cases do.
So what I propose is the following :
- the current shrinking strategy is only modifying the "len" parameter
- we provide a "pack" primitive that is resizing the array to it's "real"
size (len)  - so users with memory issues can call "pack" after having
removed a lots of elements (the user could also use to_array but that will
require him to use two different data structures for the same purpose)

> - I stole an idea from Perl, in that negative subscripts index from the
> end of the array- so get x (-1) always returns the last element of x, no
> matter how long x is.

If (-1) make some sense, I'm not so sure about (-2) and (-3) :-)
So I would prefer an explicit get_last x that is perhaps less confusing to
code readers.

And , about the name, what about Vector ? It's far more familiar that Xarray
:-)

> - No comments.  Interface is either that for Array, or hopefully
> "obvious"
>
> Note that there are still a lot of functions to write:
>
> - set, insert, and append should have _list, _array, and _xarray variants
> which only realloc once

We cannot add all the of_* , to_* and append_* for each data structure, but
an iterator can be nice :

Xarray.appendi x (List.iter l)
Xarray.appendi x (Array.iter a)
...
The problem here is that we don't know the exact size of the structure
before being enable to make a copy.
Perhaps it would be a nice start then to define some kind of data structure
generics :

type 'a iterator
val count : 'a iterator -> int (* remaining elements counter, O(1) *)
val next : 'a iterator -> 'a (* raise No_more_elements , complexity
unspecified *)
val has_more : 'a iterator -> bool (* O(1) *)
val iter : ('a -> unit) -> 'a iterator -> unit (* complexity unspecified *)
val map : ('a -> 'b) -> 'a iterator -> 'b iterator (* this is a lazy map,  I
like it ! *)

Then each data structure ( list, array, xarray, reflist ... ) will have
to_iterator, of_iterator and append_iterator (not sure about the names)
functions. For implementation, we can have :

type 'a iterator = {
    mutable count : int;
    next : (unit -> 'a);
}

Which is very simple but the data structure which is proving the "next"
function has to store it state itself.

we could define :

type ('a,'b) iterator = {
    mutable count : int;
    mutable state : 'b;
    next : ('b -> 'a * 'b);
}

but that will make the type information showing a little more about
implementation, which is meaningless to the end-user.

of maybe something like a functionnal continuation :

type 'a fnext =
    | FEnd
    | FIter of (unit -> 'a) * 'a fnext

type 'a iterator = {
    mutable count : int;
    mutable next : fnext;
}

and then :

let iter it =
    match it.next with
    | FEnd -> raise No_more_elements
    | FIter fnext ->
        let r,f = fnext() in
        it.count <- it.count - 1;
        it.next <- f;
        r

But perhaps the cost of matching and returned tuple allocation does not
worth it.
BTW Brian, if you're willing to create a SF account, I can give you rights
on the CVS.

Nicolas Cannasse