I thought about tackling this while visiting Recurse Center last year. My angle was that this could probably be most practical for a language like Erlang which comes closest to never mutating any runtime datastructure. (You might think of languages like Haskell first, but lazy evaluation cashes out to mutations in the implementation.) I seem to have misplaced my notes, or I'd link to them. Haven't gotten to trying to do this yet.

Someone at RC suggested using succinct data structures and I spent a little while studying them, but they seemed to me like they'd have more niche-y properties than a more obvious approach would.