[clean-list] Text Editor Undo and Persistent Data Structures...

[Michal Gajda]

On Mon, 28 May 2001, Fabien Todescato wrote:

> Dear Cleaners,
> 
> 	The earmark of data structures in pure functional programming
> languages is that these data structures are automatically persistent - see
> Chris Okasaki's book "Pure Functional Data Structures" p.2 -. Except maybe
> in Clean for unique data structures, unique arrays for instance.

Surely. I'd call uniques "clean, safe way of imperative destruction".

> 	Seeing that the text editor in the Clean IDE 2.0 does not support
> unlimited UNDO, I guess the underlying data structure used to manipulate
> texts is some kind of unique array. Otherwise, the different versions of the
> data structure could be stored and restored as the current version when the
> user requests an UNDO.
> 
> My question about that is : is there some deep reason why unlimited UNDO was
> not implemented in the text editor, and is it possible to use a persistent
> data structure to implement it ? Are efficient persistent data structures
> known that support : insertion and deletion in the MIDDLE of a sequence, and
> random access within a sequence.

Whereas unlimited UNDO seems to be pleasant idea, storing characters in
PF data structure not in arrays would probably lead to at least 8* as big
memory usage (I guess every node would have 2 more pointers, am I
right?). And anyway inserting text at the present position of cursor is
quite efficient with standard imperative implementation (two lists of
arrays). But there are nice(and efficient) ways to support unlimited
undos(best of them are object oriented, but what else are existentials
for :-).

	Greetings :-)
		Michal Gajda
		korek@icm.edu.pl
		*knowledge-hungry student*