Add Persistent Collections to libcollections

[Gankra]

Many people want (fully) persistent collections in Rust to make it more pure-functional friendly. Rust doesn't have GC, Laziness, or Memoization (and I don't think it should), so we can't do any of the really fancy stuff described in the oft-cited "purely functional data structures". Instead, we should go practical and simple by copying several of the structures described in Scala's Concrete Immutable Collections.

Of particular interest is:

• List: As far as I can tell this is the standard cons/cdr SinglyLinkedList every single functional language offers. I have most of an impl of this in the works using Rc, just need to write tests.
• Vector: A high-degree (32) BTree with path-copying to provide "practically constant" random access into a list
• Queue: A pair of Lists for "front" and "back", deletes take linear time when the "back" is empty, so as a fully persistent collection this is easily exploitable by an adversary!
• HashTrie: A high-degree (32) Trie over hashes with path-copying to provide a "practically constant" hashmap
• RedBlackTree: A redblack tree (presumably with path-copying?) for a treemap

Ideally, we could do something magic by genercizing over Box and Rc to reuse a lot of code between our persistent and ephemeral tree-based collections, but I'm doubtful it will be that easy.

[Gankra]

cc @aturon, would appreciate any thoughts you have on the matter

[ghost]

I have a port of Clojure's persistent vector in https://github.com/jakub-/rust-persistent-vector but it's mostly a translation rather than an idiomatic Rust implementation so it needs extra work.

[aturon]

This is definitely an area we want to explore. Just a couple of notes:

• This work needs to start out of tree in a community crate. It'll likely be a while before we'd want to land it in libcollections
• We don't have GC, true, but we do have refcounting, and laziness/memoization can be built in library code. For example, Purely functional data structures includes implementations in Standard ML, which has no built-in laziness or memoization (though it does have GC). We should be able to tackle the full range of persistent data structures.
• I agree about abstracting over smart pointers. This is another thing that will be possible with HKT, which is one of the reasons that work on persistent data structures right now is just experimental.

I'd love to see a repo started for collecting (no pun intended) some of these data structures!

[reem]

I actually began this project a week or so ago, and do have plans on continuing it. What's there so far is mostly a port of Haskell's Data.Map and a singly-linked list, but I have much more planned:

https://github.com/reem/adamantium

Laziness and Arc are really all that is needed to do cool things here. Few data structures will have complex cycles.

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/rfcs#825