Robert Dockins wrote:
On Apr 19, 2006, at 3:06 PM, Brian Hulley wrote:
Thanks. I might try this if I don't have any luck with finger trees
(from Udo's post), or if they seem too heavy for the simple thing
I'm planning to use them for (implementing the text buffer for an
edit control which needs a mutable array of lines where each line
contains a mutable array of character info). I don't need non-Int
indices so your data type for Vector would be fine.
In that case, you may be interested in this paper, which discusses a
data structure specifically designed for strings called 'ropes':
http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/
issue12/spe986.pdf
I'm not aware of a Haskell implementation of ropes, but there may
well be one floating around. Actually, I'd be kind of surprised if
someone hasn't implemented this already (does YI use ropes?); it
seems like such a great fit for Haskell.
Thanks, I'll look into this paper too.
Incidentally, there are quite a lot of interesting issues that come up with
the task of implementing an edit control (or any other user interface
element) in Haskell. For example, if the user types several characters, a
naive implementation would enter each character individually into the text
buffer, resulting in a sequence of updates, even though the control would
not be re-rendered until there are no more (character) messages left in the
message queue, whereas another way is to represent the operations explicitly
eg Insert 'b' (Insert 'a' (Buffer ...)) so that this can be optimized to
InsertString "ab" (Buffer ...) resulting in only one update before the
control is re-rendered...
Best regards, Brian.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
