[Haskell-cafe] Mutable data design question

[Ben Rudiak-Gould]

GoldPython wrote:

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

I wouldn't say that textual data is by its nature mutable. That's just 
the imperative way of looking at it. The functional way is to think of 
all possible documents as Platonic entities -- the books in Borges's 
library -- and of writing a document as the process of choosing which 
book you want. When you insert or delete a character you're moving your 
attention from one book to a nearby one. The problem then is finding a 
way of representing books as values in your program in such a way that 
"nearby" books, in the above sense, have similar values that can take 
advantage of sharing. The typical approach is to describe each book 
inductively as the concatenation of several smaller ones, bottoming out 
at short phrases (say). Then when you add or delete a character, only 
one sub-book has changed, and in that sub-book only one sub-sub-book has 
changed, and so on, so you only need to replace one index at each level, 
which costs a logarithmic amount of work.

-- Ben