[Haskell-cafe] Advice needed on best way to simulate an STL vector
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:
>> 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
> 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