scala - Purely functional data structures for text editors

Question

What would be good purely functional data structures for text editors? I want to be able to insert single characters into the text and delete single characters from the text with acceptable efficiency, and I would like to be able to hold on to old versions, so I can undo changes with ease.

Should I just use a list of strings and reuse the lines that don't change from version to version?

question from:https://stackoverflow.com/questions/12358083/purely-functional-data-structures-for-text-editors

Answer 1

A Vector[Vector[Char]] would probably be a good bet. It is an IndexedSeq so has decent update / prepend / update performance, unlike the List you mention. If you look at Performance Characteristics, it's the only immutable collection mentioned that has effective constant-time update.