<p>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: <a href="http://en.wikipedia.org/wiki/Operational_transformation" rel="nofollow">http://en.wikipedia.org/wiki/Operational_transformation</a></p>

CC BY-SA 2.5
2011-01-04T21:18:54.257Z
This is higher level than I was asking at but incredibly helpful and probably the best answer that exists.
Jonathan
CC BY-SA 2.5
2011-01-04T15:38:41.390Z
2011-01-04T15:38:41.390Z
sclv
<p>I'm looking for a confluentially persistent data structure for a string - so far I'm looking at <a href="http://www.soi.city.ac.uk/~ross/papers/FingerTree.pdf" rel="nofollow">finger trees</a>. 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.</p>

<p>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.</p>

<ds.data-structures><functional-programming>
Confluently Persistent String Data Structure
Jonathan
# Confluently Persistent String Data Structure

(Asked by: username_0 on 2011-01-03)

I'm looking for a confluentially persistent data structure for a string - so far I'm looking at [finger trees](http://www.soi.city.ac.uk/~ross/papers/FingerTree.pdf). 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.

**Tags:** ds.data-structures, functional-programming


---

## 1 answers

### Answer by username_1 on 2011-01-04. Score: 5 | Accepted answer

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>

> **Comments:**
> **username_0**: This is higher level than I was asking at but incredibly helpful and probably the best answer that exists.  

---

