[Haskell-cafe] Mutable data design question
Marcin 'Qrczak' Kowalczyk
qrczak at knm.org.pl
Fri Dec 3 12:22:41 EST 2004
GoldPython <goldpython at gmail.com> writes:
> In the case of writing something like a text editor where the data
> involved is by its very nature mutable, what sort of design paradigm
> would you use in a functional language?
This is specific to text editors:
1. Use a traditional mutable data structure, e.g. IOArray of IOUArrays
(lines), each coupled with "first filled" and "last filled" indices
and resized when needed. Implement "undo" by the list of changes.
Easy conceptually. Has good performance in common cases and poor
performance for unusual data (e.g. very long lines). Easy to make
bugs in undo handling.
2. Use a persistent data structure with logarithmic cost of most
operations: a balanced tree of text fragments, called a rope
(Hans Boehm has made one for C). "Undo" can be made by simply
keeping old versions.
Hard to implement the core data structure. If done right, the rest
is easy, in particular "undo" handling is very robust. There are
some overheads for all operations, but the cost of operations
scales to extreme cases.
The second way is more interesting, but I don't know how to implement
a rope in details.
__("< Marcin Kowalczyk
\__/ qrczak at knm.org.pl
More information about the Haskell-Cafe