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::ConsList], and [im::List] (im version 9.0.0) with the get, cons, and uncons operations:

test get_fral ... bench: 35,129 ns/iter (+/- 162) test get_im_conslist ... bench: 37,545,651 ns/iter (+/- 1,089,092) test get_im_list ... bench: 452,968,129 ns/iter (+/- 14,544,638) test cons_fral ... bench: 295,407 ns/iter (+/- 414) test cons_im_conslist ... bench: 172,356 ns/iter (+/- 437) test cons_im_list ... bench: 580,119 ns/iter (+/- 14,259) test uncons_fral ... bench: 51 ns/iter (+/- 0) test uncons_im_conslist ... bench: 17 ns/iter (+/- 0) test uncons_im_list ... bench: 438 ns/iter (+/- 1)