Finger Trees Explained Anew, and Slightly Simplified (Functional Pearl)
summary
Stepwise refinement shows why Hinze and Paterson’s Finger Tree needs one-or-three-element buffers and nodes of two-or-three values, claims a simplified implementation, and proves worst‑case logarithmic time for cons/tail/append and amortized constant time for head/tail/cons/last/insert. The construction uses implicit recursive slowdown (pairing elements into a faster recursive layer), small helper functions like toTuples and glue, QuickCheck for correctness, and one concrete simplification: it adds a three-element case to the fingers to obtain the amortized bounds.
AI-written summary · about
chapters (4)
related talks
32mFunctional implementation of Finger Trees in JavaScript
24mTruly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)
10mFunctional Data Structures
01h 32mAlgorithms for Trees - Foldable, Applicative, Traversable
50mData Structures of the Dark Side
48mPurely Functional Data Structures
28mLightweight Testing of Persistent Amortized Time Complexity in the Credit Monad
28mDesign Patterns for Parser Combinators (Functional Pearl)