[Haskell-cafe] Advice needed on best way to simulate an STL vector
brianh at metamilk.com
Wed Apr 19 16:05:43 EDT 2006
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':
> 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.
More information about the Haskell-Cafe