Are the rules of routine borrowing in the way of functional data structures?

Question

Functional data structures (such as the Hash Array Mapped Trie used in Haskell / Clojure / Scala) are based on a lot of sharing in the underlying data structure. For example, if we implement insert as a map type, which is usually implemented by copying a path on a tree that implements a data structure.

Given that these data structures are highly dependent on the sharing (and the primary owner) of the base values, will borrowing interfere with the implementation of such structures?

Answer 1

Short answer: None .

Long answer:

Rust really works very well with immutable structures (this gives more guarantees than C const , for example).

Co-ownership is not a problem ( Rc / Arc ) with a truly immutable value, and you can easily borrow several times into an immutable structure. You cannot move while borrowing, but you can get around this by passing proxy owners (via Rc or Arc again) instead of links.

One problem in Rust that you might not have in Haskell is mixing variable values ​​with Cell or RefCell , since you can create loops and they won't be built because Rust doesn't have a GC.