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 listQueue: 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" hashmapRedBlackTree: 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.
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 standardcons/cdrSinglyLinkedListevery 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 listQueue: 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" hashmapRedBlackTree: A redblack tree (presumably with path-copying?) for a treemapIdeally, 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.