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

[Udo Stenzel]

Brian Hulley wrote:
> In C++, STL provides a vector class which behaves as an array except you 
> can insert/delete elements from it.

Though you shouldn't.  If you constantly insert and delete in the middle
of a std::vector, you're not using the right data structure.  In fact,
std::vector is almost always wrong and std::deque would probably serve
you better.


> I'm wondering what is the best Haskell 
> data structure to use to simulate this, either mutable or immutable.

The obvious mutable data structure is an (STRef (STArray i a)).  You can
implement std::vector in terms of that, almost literally translating
from C++.  If you want Haskell code that looks as ugly as C++, you
should do exactly that.

Immutable array-like thing with insertion and deletion are an
ill-conceived idea, imho.  Every write operation would require a
complete copy and often a reallocation, too.

Instead, use some functional sequence implementation, like Finger Trees.
Operations in the middle of the sequence incur a logarithmic cost, but
thats better than constantly copying the whole thing around.  Being
immutable it also results in more idiomatic code where you don't need to
drag the ST monad around everywhere.  You might also consider a
Finger Tree of smallish Arrays, that's about the closest equivalent to
std::deque you can get.


Udo.
-- 
"In the software business there are many enterprises for which it is not
clear that science can help them; that science should try is not clear
either."
	-- E. W. Dijkstra
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060419/f19752f9/attachment.bin