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

[Udo Stenzel]

Brian Hulley wrote:
> in my particular case (which was a text buffer 
> for an edit control implemented as a std::vector of lines where each line 
> contains some book-keeping info plus a std::vector of character info)
> [...]
> I'm keen to learn what the Haskell way is rather than just porting my old 
> C++ code directly.

Well, in this case I'd even say the Haskell way and the C++ way
coincide.  The best data structure is a rope (not standard in C++, but
widely available), which is basically a (balanced) tree of small
immutable strings that can share substrings.

Ropes provide indexing, concatenation and substring extraction with
logarithmic costs and traversal in amortized linear time.  Operations
through iterators have amortized constant cost, and the overall cost is
quite low.  They work best with garbage collection and actually sound
very Haskellish.  You could even dump your whole text into a single
rope, you don't need to split it into lines.  In fact, a text editor
implemented in exactly this way is the major selling point of the Rope
library.

We don't have an implementation of Ropes (yet?).  I think, a Finger Tree
of Fast Packed Strings might be the closest thing.  I'd even implement
it this way, if the low performance of raw Strings finally overcame my
inertia...


> A reallocation 
> (amortized cost O(0)) and copy (a simple memcpy) might be very fast 

Doing a memcpy every time a character is inserted is a Bad Thing.  It
gets slower the longer the edited line is.  Vim seems to do something
like that and I positively hate this behavior.  Use two Ropes instead
(or two Finger Trees) and the cost becomes amortized O(1).


> Thanks, I've downloaded a paper about them from 
> http://www.informatik.uni-bonn.de/~ralf/publications/FingerTrees.pdf so 
> I'll see if I can understand it! Looks interesting...

Even better, thanks to Ross Paterson you can get code at
http://www.soi.city.ac.uk/~ross/software/html/Data.Sequence.html or
simply get a recent version of GHC:
http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Sequence.html


Udo.
-- 
Fuchs zu sein heißt nicht nur, einen Schwanz zu haben...
	-- Gipfelbuch auf dem Postakegel
-------------- 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/2e66147a/attachment.bin