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

[Brian Hulley]

Sebastian Sylvan wrote:
> On 4/19/06, Brian Hulley <brianh at metamilk.com> 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.