I think what we need is immutable data-structures to be shareable between threads. This approach should also allow structural sharing between threads, allowing for efficient and safe data structures.
Also, I could see a use for a mechanism where a thread creates a data-structure, then marks it as read-only, such that it can become shared.