Re: [Haskell-cafe] Advice needed on best way to simulate an STL vector

Sebastian Sylvan wrote:

On 4/19/06, Brian Hulley wrote:

...

[snip] 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?

Well not efficient in the C++ sense. You'd still have to create a whole new array for all of those operations. You can use the (//) operator to update all the elements you need to update...

insert i xs arr = arr // shift_list where n = length xs shift_list = zip [i..] xs ++ [ (j,arr!(j - n)) | j <- [i+n .. snd (bounds arr)]]

Thanks, but I think this would be too slow, unless the compiler could somehow optimize out the list argument from // . I imagined that insert/delete would just use C memcpy internally to quickly blit the cells up or down.

...

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)?

Well that depends on what you're doing. Mutable arrays are more efficient for most operation (replace is O(1) instead of O(n), for example), but it's possible that for small arrays immutable has a smaller constant factor (I'm certainly not sure that it does!)

I was thinking perhaps generational garbage collection suffers badly when faced with mutable arrays but perhaps I'm wrong or it is not a necessary consequence of using mutable data structures. Best regards, Brian.