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

Brian Hulley brianh at metamilk.com
Wed Apr 19 15:17:53 EDT 2006

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. 

More information about the Haskell-Cafe mailing list