Sebastian Sylvan wrote:
On 4/19/06, Brian Hulley <[EMAIL PROTECTED]> 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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
