This file implements finger trees, a
functional data structure that provides efficient access to both
ends of a sequence and supports efficient concatenation and
splitting operations.
A finger tree is a tree where the "fingers" point to the ends,
allowing O(1) access to the front and back elements, and O(log n)
complexity for most operations, including adding front and back,
and also the concatenation.
The structure consists of:
Empty: an empty finger tree
Single: a finger tree with exactly one element
Deep: a finger tree with a prefix (1-3 elements), a middle finger
tree of nodes, and a suffix (1-3 elements)
Example
import*asFTfrom"#src/utils/finger_tree.api.js";
constempty = FT.empty; constsingle = FT.single(42); consttree = FT.cons(FT.snoc(single, 100), 10); // tree now contains [10, 42, 100]
This file implements finger trees, a functional data structure that provides efficient access to both ends of a sequence and supports efficient concatenation and splitting operations.
A finger tree is a tree where the "fingers" point to the ends, allowing O(1) access to the front and back elements, and O(log n) complexity for most operations, including adding front and back, and also the concatenation.
The structure consists of:
Example