I still definitely agree that having Dynarrays to work with would be good. Even if it has a little lack of efficiency for now. It could definitely be improved.
I find it odd that with multicore around the corner people are still looking for a mutable data structure. I think that persistent vectors along the lines of RRBs would be a much better tool to add to the box.
I once started an implementation here but never got around to finish it. My motivation was mainly to have a nice data structure to support Unicode text (see Utext) as vector of Uchar.t values with a good uniform data structure to move across the different segmentation of text you might need: sequences of scalar values, sequences of grapheme clusters, sequences of lines, sequences of paragraphs and any combination thereof by piling the vectors on top of each other.
4 Likes
I don’t think anyone’s particularly looking for a mutable data structure. What I see is a bunch of algorithms out there assuming extensible arrays. Being able to translate them to ocaml effortlessly and moving on would be the main goal here.
4 Likes
A dummy value could be provided by the module if it is acceptable to use a function instead of simple polymorphism.
And yes, I agree that backing it by an 'a option array is a good idea, as the implementation will take 5 minutes.
It’s possible to sit back an come up with a perfectly optimised implementation after the flawed one is up and running
Mutable data structure are a core part of OCaml IMO
And I think a dynamic array is such a simple and ubiquitous feature that it needs to be in the std lib
Your data structure certainly looks interesting though, thank for the share
The standard library is mostly append only. Starting with a bad implementation incurs the risk of getting stuck with the bad implementation for a very long time.
3 Likes
What is the status of this implementation?
If we want dynamic arrays in the stdlib, I think that the work to be done has been clearly outlined: someone needs to do the work of writing a document that:
- collects pointers to existing resizable-array implementations out there (I believe several have already been mentioned in this thread),
- compares the APIs and discuss the important differences
- presents the choices (on the interesting differences) that are proposed for the stdlib
- (possibly as a second step) proposes an implementation, possibly by reusing code from licence-compatible existing implementations
Before an implementation is written, the authors of this document should feel free to seek feedback on the proposed design, here or in the original PR.
Doing this takes work, but it would also be useful.
4 Likes