# Crate fral [−] [src]

# Functional random-access lists

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`

.

### 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 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)
```

# Examples

use fral::Fral; // 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)] );

## Modules

rc |
An |

## Structs

Fral |
An |

Iter |

## Traits

AsArc |
Automatic |