Module finger_tree.api

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)
import * as FT from "#src/utils/finger_tree.api.js";

const empty = FT.empty;
const single = FT.single(42);
const tree = FT.cons(FT.snoc(single, 100), 10);
// tree now contains [10, 42, 100]

Index

Variables

Functions