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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.