Immutables

Immutables implements several immutable, or persistent, data structures for R: operations return modified copies while remaining fast and true to R’s side-effect-free functional nature with list-like semantics.

• flexseqs provide list-like operations:
  • indexed and named element access
  • push/pop/peek from either end for double-ended queue behavior
  • efficient insertion, splitting, and concatenation
• priority_queues associate items with priority values and provide min and max peek/pop by priority and fast insertion.
• ordered_sequences associate items with key values and keep the elements in sorted order by key. These may be similarly be inserted/popped/peeked by key value as well as position. Keys may be duplicated, with first-in-first-out order within key groups.
• interval_indexes store items associated with interval ranges, supporting point as well as interval overlaps/contains/within queries. Items are kept in start-order enabling ordered sequence operations and sweep-line algorithms.

Speed and Flexibility

Backed by monoid-annotated finger trees as described by Hinze and Paterson, most operations are constant time, amortized constant time, or $O(\log(n))$. Core functions are implemented in C++ (via Rcpp) for speed, with matching pure-R reference implementations using lambda.r syntax similar to the paper’s Haskell.

The developer API supports the addition of custom structures via combinations of monoids and measures. See the full documentation for vignettes and reference, including a gallery of worked examples and benchmarks.