函数式随机访问列表 (fral)

[dependencies]
fral = "1.0"

函数式随机访问列表是一种有效的数据结构，具有 O(log n) 的 查找 和 更新 操作，以及 O(1) 的 cons 和 uncons 操作，同时保留原始列表。它由Chris Okasaki在1995年的ACM FPCA论文《Purely Functional Random-Access Lists》中引入。

我们提供了基于 Arc 和 Rc 的实现，分别位于 Fral 和 rc::Fral，具体取决于您的使用场景。由于 Arc 是最通用的，它是此软件包的“主要”实现。但是，如果您不需要线程安全性，请使用 rc::Fral（它是对 Fral 的直接替换），因为它具有更小的开销。

使用方法

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) {
    assert_eq!(*x, 1);
} else { unreachable!() }
// lookup out of bounds is O(1)
assert_eq!(f.get(5), None);

// uncons is O(1)
if let Some((head, tail)) = f.uncons() {
    assert_eq!(*head, 5);
    assert_eq!(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<_>>(),
    vec![Arc::new(5), Arc::new(4)]
);

与 im 的比较

以下是与 Fral、im::Vector、im::CatList 和 im::ConsList（im 版本 10.0.0）的基准结果，使用 get、cons 和 uncons 操作（对于 im::Vector，它们是 push_front 和 pop_front）。结果按效率排序。

test get_im_vector      ... bench:      25,968 ns/iter (+/- 113)
test get_fral           ... bench:      37,356 ns/iter (+/- 124)
test get_im_catlist     ... bench:  15,397,279 ns/iter (+/- 375,877)
test get_im_conslist    ... bench:  36,834,300 ns/iter (+/- 1,073,303)

test cons_im_conslist   ... bench:     170,603 ns/iter (+/- 461)
test cons_fral          ... bench:     294,475 ns/iter (+/- 195)
test cons_im_catlist    ... bench:     641,423 ns/iter (+/- 2,625)
test cons_im_vector     ... bench:     949,886 ns/iter (+/- 6,663)

test uncons_im_conslist ... bench:          17 ns/iter (+/- 0)
test uncons_fral        ... bench:          52 ns/iter (+/- 0)
test uncons_im_catlist  ... bench:         149 ns/iter (+/- 0)
test uncons_im_vector   ... bench:         454 ns/iter (+/- 2)