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

Greg Fitzgerald garious at gmail.com
Wed Apr 19 16:55:09 EDT 2006


> 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.

text s = mySort s [] []

mySort      []     stack     sorted  = (reverse sorted) ++ stack
mySort ('R':xs)       []     sorted  = mySort xs       []     sorted
mySort ('R':xs) (s:stack)    sorted  = mySort xs    stack  (s:sorted)
mySort ('L':xs)    stack         []  = mySort xs    stack         []
mySort ('L':xs)    stack  (s:sorted) = mySort xs (s:stack)    sorted
mySort   (x:xs)    stack     sorted  = mySort xs    stack  (x:sorted)

Here's how it works:
The string 's' in the 'text' function is a string of numbers (sorry, my app
only needed to handle numbers) and two special characters 'L' and 'R' which
translate to MoveCursorOnePositionRight and MoveCursorOnePositionLeft

In 'mySort', numeric characters in the input stream are pushed onto the
'sorted' stack.    A 'Left' movement causes the head of the 'sorted' stack
to be transferred to 'stack'.  A 'Right' movement causes the head of the
'stack' to be transferred to 'sorted'.  At the end of the input stream, the
characters to the right of the cursor (the characters in 'stack') are
appended to the characters to the left of the cursor (the reverse of

I'm new to Haskell so maybe Ropes are better, but if the problem you need to
solve is as simple as mine, it's hard to read research papers when you can
get the job finished with 7 lines of Prelude code.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org//pipermail/haskell-cafe/attachments/20060419/9ca7bef0/attachment-0001.htm

More information about the Haskell-Cafe mailing list