Functional random-access lists (fral)

toml [dependencies] fral = "1.0"

A functional random access list is an efficient data structure with lookup and update operations in O(log n), and cons and uncons operations in O(1) while preserving the original list. It was introduced in Chris Okasaki's 1995 ACM FPCA paper [Purely Functional Random-Access Lists].

We provide [Arc]-based and [Rc]-based implementations in [Fral] and [rc::Fral], depending on your use-case. Because [Arc] is the most versatile, it is the "primary" implementation for this crate. However, if you don't need thread-safety, [rc::Fral] has less overhead and should be used instead — it is a drop-in replacement for [Fral].

Usage

```rust extern crate fral; use fral::Fral; use std::sync::Arc;

// cons is O(1) let mut f = Fral::new(); for item in vec![1, 2, 3, 4, 5] { f = f.cons(item); }

// lookup is O(log n) if let Some(x) = f.get(4) { asserteq!(*x, 1); } else { unreachable!() } // lookup out of bounds is O(1) asserteq!(f.get(5), None);

// uncons is O(1) if let Some((head, tail)) = f.uncons() { asserteq!(*head, 5); asserteq!(tail.len(), 4); } else { unreachable!() }

// in this scope, we want f to have an extra item in front. // we can do this in O(1), without cloning any items. { let f = f.cons(42);

assert_eq!(*f.get(0).unwrap(), 42);
assert_eq!(*f.get(5).unwrap(), 1);

}

// our original Fral is still here assert_eq!( f.iter().take(2).collect::>(), vec![Arc::new(5), Arc::new(4)] ); ```

Comparison with im

The following are benchmark results against [Fral], [im::Vector], [im::CatList], and [im::ConsList] (im version 10.0.0) with the get, cons, and uncons operations (which are push_front and pop_front for im::Vector). Results are sorted by efficiency.

``` test getimvector ... bench: 25,968 ns/iter (+/- 113) test getfral ... bench: 37,356 ns/iter (+/- 124) test getimcatlist ... bench: 15,397,279 ns/iter (+/- 375,877) test getim_conslist ... bench: 36,834,300 ns/iter (+/- 1,073,303)

test consimconslist ... bench: 170,603 ns/iter (+/- 461) test consfral ... bench: 294,475 ns/iter (+/- 195) test consimcatlist ... bench: 641,423 ns/iter (+/- 2,625) test consim_vector ... bench: 949,886 ns/iter (+/- 6,663)

test unconsimconslist ... bench: 17 ns/iter (+/- 0) test unconsfral ... bench: 52 ns/iter (+/- 0) test unconsimcatlist ... bench: 149 ns/iter (+/- 0) test unconsim_vector ... bench: 454 ns/iter (+/- 2) ```