Purely Functional Data Structures in Rust
Rationale
Purely functional data structures have the persistence property. The data structure is a collection of delta updates on top of previous updates. They are immutable and as such, they are very suitable solution for a large set of problems in distributed systems, concurrent systems and databases, ...
What's in there
- List or Stack
- Queue
- Balanced Set
- Balanced Map
- Hash Set
- Hash Map
- Tree
What's excluded
Map
/Set
/Queue
iter
are not yet implemented. They are available for List
/HashSet
/HashMap
/Tree
however.
Example
let mut numbers = Vec new;
let mut n = empty;
for _ in 0..1000000
let mut sorted = numbers.clone;
sorted.sort;
sorted.dedup;
assert_eq!;
for i in 0..numbers.len
let mut v = n.to_vec;
v.sort;
assert_eq!;
for i in sorted
assert_eq!;
Test coverage
The tests aim for 100% test coverage. 100% coverage doesn't exclude bugs. In fact it uncovered bugs in the coverage tool (tarpaulin), so use it at your own risk ;) Also, given the fragile status of tarpaulin, there are a lot of false positive: code marked as uncovered, but it is.
Credits
Bot set.rs & map.rs are highly inspired by the F# code in the F# compiler code (FSharp.Core/set.fs). The F# code is one of the highest performance implementations out there.
License
BSD-3-Clause license