Confluently Persistent String Data Structure I'm looking for a confluentially persistent data structure for a string - so far I'm looking at finger trees. That is, how would I resolve two edits to the same base tree, and would I be able to preserve the undo history? I'm assuming that some mutations would be mutually exclusive, and I'd need to reject one. That is, I'm under the impression that order matters.

Some specifics - I'll have a copy of the tree in each thread - each will be sending updates to a central thread that updates all the others. Each thread will be based on the central thread's tree.
What you seem to be looking for is not a data structure for strings themselves, but a grammar for representing concurrent actions on strings. The field of study for this is Operational Transformation: http://en.wikipedia.org/wiki/Operational_transformation