Immutables-package: Immutables: Fast and Functional Data Structures

In Immutables: Fast and Functional Data Structures

Immutables: Fast and Functional Data Structures

Description

The Immutables R package implements several immutable, or persistent, data structures: operations return modified copies while remaining fast and true to R's side-effect-free functional nature.

Details

• flexseqs provide list-like operations: indexed and named element access; push/pop/peek from either end for double-ended queue behavior; 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.

Backed by monoid-annotated 2-3 fingertrees 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 to match the paper.

Finally, the developer API supports the addition of custom structures via combinations of monoids and measures.

• Hinze, R. and Paterson, R. (2006), Finger trees: a simple general-purpose data structure. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1017/S0956796805005769")}

Author(s)

Maintainer: Shawn T. O'Neil [e-mail]

See Also

Useful links:

• https://oneilsh.github.io/immutables/

• https://github.com/oneilsh/immutables

• Report bugs at https://github.com/oneilsh/immutables/issues

Immutables documentation built on April 29, 2026, 1:06 a.m.