[Haskell-cafe] Mutable data design question

[Marcin 'Qrczak' Kowalczyk]

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
    ^^     http://qrnik.knm.org.pl/~qrczak/