Do Rust's borrowing rules get in the way of functional data structures?

Question

Functional data structures (such as the Hash Array Mapped Trie used in Haskell/Clojure/Scala) rely on lots of sharing in the underlying data structure. For example, if we implement insert on a map-like data type that's usually implemented by path-copying on the tree that implements the data structure.

Given that these data structures rely a lot on sharing (and no principal owner of) underlying values, will borrowing get in the way of implementing such structures?

Answer 1

Short Answer: No.

Long Answer:

Rust actually works very well with immutable structures (it gives more guarantees than C's const for example).

The shared ownership is no problem (Rc/Arc) with a truly immutable value, and you can easily borrow multiple times into an immutable structure. You cannot move while borrowing, but this can be circumvented by handing out owning proxies (via Rc or Arc once again) instead of references.

The one issue in Rust that you may not have in Haskell is mixing mutable values in with Cell or RefCell as you can then create cycles and those won't be collected because Rust has no GC.