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

[Sebastian Sylvan]

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

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

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

/S

--
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862