Add Persistent Collections to libcollections

Issue by Gankro
Friday Aug 15, 2014 at 15:09 GMT

For earlier discussion, see https://github.com/rust-lang/rust/issues/16521

This issue was labelled with: A-libs in the Rust repository

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.

No implementation files or tests are named. Start by reviewing the earlier discussion in rust-lang/rust issue 16521 and the proposed List, Vector, Queue, HashTrie, and RedBlackTree designs. Done would require an agreed scope and implementation plan for persistent collections in Rust.