On 06-Jul-1999, Marcin 'Qrczak' Kowalczyk <[EMAIL PROTECTED]> wrote:
> What do you think would be the best representation of the buffer for
> such a crazy idea as a text editor in Haskell?
> 
> The first choice: mutable or not. If it were pure functional, like
> GHC's FiniteMap, it would be easy to implement undo: just store
> various buffer states in a list, hoping that the underlying structure
> will share most of the unchanged state. I'm just afraid it will be
> too inefficient without a really good structure.
> 
> Hmm, what about a balanced tree:
> 
> data Buffer = Buffer Int{-total length-} Contents
> data Contents = Branch Buffer Buffer | Leaf LeafString
> type LeafString = some suitable String-like type (which?)
> 
> If I am able to correctly think in the hot Poland, it would give
> logarithmic time and space cost for each update. A String-like type
> instead of `Leaf Char' reduces the constant factor. The cost would
> also be logarithmic wrt total buffer length for a single insertion or
> deletion of a large substring, and when we repeatedly insert a single
> character near the same place and store in the undo buffer only the
> state before all the insertions, the space cost is almost constant wrt
> the number of insertions, only logarithmic wrt total buffer length.
> The time cost for examining a substring is also logarithmic.
> 
> Am I right? And is such a logarithmic cost for an editor good enough
> for practice? Does anybody see a better solution? Is it already
> implemented somewhere?

The Boehm (et al) conservative garbage collector includes a `cord' type
which is a tree-based representation of strings, similar to the one you
describe.  The collector includes a primitive editor implemented using
this type.  The documentation says the following:

 | de.c is a very dumb text editor that illustrates the use of cords.
 | It maintains a list of file versions.  Each version is simply a
 | cord representing the file contents.  Nonetheless, standard
 | editing operations are efficient, even on very large files.

The Boehm collector is available via <http://reality.sgi.com/boehm/gc.html>.

I have heard that the latest versions of the SGI STL C++ library include a
`rope' data type which is, I believe, based on the same kind of idea,
but I don't know the details.

-- 
Fergus Henderson <[EMAIL PROTECTED]>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger [EMAIL PROTECTED]        |     -- the last words of T. S. Garp.


Reply via email to