[Haskell-cafe] Advice needed on best way to simulate an STL vector

Brian Hulley 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':
>
> 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. 



More information about the Haskell-Cafe mailing list