Well, you could use something like C++ does for implementing STL vectors in terms of arrays -- iirc, it generally doubles the allocated size each time applying an operation to the vector would make it exceed its capacity (the current allocation size), and keeps track of the actual number of elements stored separately. It's important to do allocation which is proportional to the existing capacity, or repeated insertion will become quadratic time rather than linear. So essentially, some data structure like
data Vector a = Vector { store :: Array Int a, end :: Int } would be a sufficient minimal way to start. When the store needs to be increased, you simply create a new array with twice as many elements, copy the initial elements in from the old array which is then thrown away, and only update end to the position of the actual last element. This is analogous to what C++ implementations of the vector class do. What will bite you is if you try to generalise from indices of type Int to instances of Ix -- the Ix operations assume that there are lower and upper bounds on indices. The upper bound of course quickly becomes a problem. You could however use Enum, which has toEnum and fromEnum, which are sufficient to use with the implementation in terms of Ints. It could also be claimed that Int isn't always the best initial type to use, and indeed I'd still feel safer with Integer somehow, but then, fromEnum and toEnum use Int, and if you have more than 2 billion elements in your vector at the same time, maybe you should be looking at your algorithm more carefully and/or doing your own low level memory allocation via FFI. :) - Cale On 19/04/06, Brian Hulley <[EMAIL PROTECTED]> wrote: > Hi - > In C++, STL provides a vector class which behaves as an array except you can > insert/delete elements from it. I'm wondering what is the best Haskell data > structure to use to simulate this, either mutable or immutable. > > I've looked at the Array interface, but although there is the // operation > to replace some elements, there does not appear to be a simple way to > delete/insert elements. > > Ideally I'd like functions like: > > -- Insert new elements starting at the specified index, moving the others up > to make room > insert:: Array i e -> i -> [e] -> Array i e > > -- Delete a range of elements, moving later elements back down > delete:: Array i e -> i -> i -> Array e > > -- Append a new element to the end of an array > push_back :: Array i e -> e -> Array i e > > Is there an efficient way of implementing these operations in Haskell, based > on arrays, or should I be using some other data structure altogether eg a > list? > > Also, for large arrays, am I right in thinking that it is still more > efficient to use immutable arrays rather than mutable arrays (because it is > easier for gc to always just deal with immutable values)? > > Thanks, Brian. > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe