I'm experimenting with a toy (functional) programming language. One of my ideas is to aggressively hash cons everything, thus representing any data structure as a single integer. In that context, data structures are only efficient if they are history independent so I would switch out traditional RB/AVL/weight balanced trees for PATRICIA trees. For example, any set S would then be represented by the same underlying integer regardless of how it had been made.
A modern editor for my language (e.g. with throwback of inferred types) could benefit from "free" incremental updates to lexing, parsing and even type checking in the event of insertions and deletions of characters in the input program provided I can use a history-independent data structure supporting efficient enumeration, insertion and deletion.
Therefore, I am wondering if there is a history-independent rope?