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

[Brian Hulley]

On Wednesday 19th April 2006 21::55 Greg Fitzgerald wrote:
> Brian,

> > implementing the text buffer for an edit control

> Just a few weeks ago I was thinking about a functional way to
> implement an edit control.  I ended up with the code below.
> The function 'text' takes a stream of  user input and returns the
> text to be displayed.

> Rather than using a mutable buffer, I chose to implement this
> using a stream of user input and two stacks where each stack
> contains the characters on opposite sides of the cursor.
>  I'm certainly no expert, but I believe all operations are constant
> time, except that returning the final string at the end of the input
> stream is O(n).  Of course, if you have a huge amount of text
> to display and need to display it after each key is pressed,
> then this is pretty worthless.
> [snip]

Thanks! I see you are representing the text buffer from the point of view of 
the cursor therefore all edit ops are constant time or O(k) where k is the 
numbers of chars involved in the change (eg for cut and paste).
Some ops such as clicking the mouse on a different part of the text after 
scrolling up/down would be O(n) in the difference between the old and new 
cursor position, but since most editing is presumably sequential, perhaps 
the amortized cost would still be constant.

I think this would also work even for very large texts, because many things 
can probably be done without having the create the whole string each time, 
but I'll have to try it out to see how it works in practice.

In any case it is a very useful pattern to make use of the locality of 
editing to get such a direct and efficient purely functional representation. 
Before I was just looking at the data structure from a "bird's eye" view, 
but I see the key to functional efficiency here is to represent it from a 
place where everything non-local is not changing ie from the point of change 
itself...

Thanks for this pattern,
Brian.