Incremental Algorithms on Lists

Incremental computations can improve the performance of interactive programs such as spreadsheet programs, program development environments, text editors, etc. Incremental algorithms describe how to compute a required value depending on the input, after the input has been edited. By considering the possible different edit actions on the data type lists, the basic data type used in spreadsheet programs and text editors, we define incremental algorithms on lists. Some theory for the construction of incremental algorithms is developed, and we give an incremental algorithm for a more involved example: formatting a text. CR categories and descriptors: D11 [Software]: Programming Techniques --- Applicative Programming, D43 [Software]: Programming Languages --- Language constructs, I22 [Artificial Intelligence]: Automatic Programming --- Program transformation. General terms: algorithm, design, theory. Additional keywords and phrases: Bird-Meertens calculus for program construction, incremen..