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?
How to improve the above? What String-like type to use in GHC?
What balance invariant to use?
The above structure does not try to treat '\n's in a special way, so
going up and down through the lines could be quite expensive. Or maybe
not, if the following will work (am I right that this is the case where
++ would give quadratic cost? I don't quite understand the difference):
substrFrom :: Buffer -> Int -> String
substrFrom buf i = substrFrom' buf i "" where
substrFrom' (Buffer _ cont) i = case cont of
Branch (Buffer len1 buf1) (Buffer len2 buf2) ->
if i < len1 then
substrFrom' buf1 i . substFrom' buf2 0
else
substrFrom' buf2 (i - len1)
Leaf str -> (drop i str ++)
How fast would be `length $ takeWhile (/= '\n') $ substrFrom buf i'?
Is there a better structure?
--
__("< Marcin Kowalczyk * [EMAIL PROTECTED] http://kki.net.pl/qrczak/
\__/ GCS/M d- s+:-- a22 C+++>+++$ UL++>++++$ P+++ L++>++++$ E-
^^ W++ N+++ o? K? w(---) O? M- V? PS-- PE++ Y? PGP->+ t
QRCZAK 5? X- R tv-- b+>++ DI D- G+ e>++++ h! r--%>++ y-