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
signature.asc
Description: Digital signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe