Functional implementation of Finger Trees in JavaScript
summary
A complete, purely functional Finger Tree implemented in a narrow subset of JavaScript and demonstrated inside an ObservableHQ workbook, including cons and snoc, folding, cached sizes and a generic measure so searches work by index or by weight. Implementation uses digits (1–4), internal nodes of 2 or 3, and pushes overflow nodes down; sizes are cached for O(1) size access and searches become logarithmic while many updates are amortized constant. Visualizer and merge procedure run and illustrate growth up to size 26.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:48What is finger tree
- 4:05How finger tree grows
- 6:05Ordered monoids
- 7:40Serialization
- 10:38Cons
- 13:23Build
- 16:18Fold
- 20:08Size
- 21:38Index
- 23:03Find
- 23:41Measure
- 25:49Nodes
related talks
24mTruly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)
01h 03mFunctional Programming in JavaScript
39mFun with Functional JavaScript
49mGoing Functional with JS
27mFrom Zero to Binary Search Tree
33mImmutable data structures for functional JS
01h 32mAlgorithms for Trees - Foldable, Applicative, Traversable
10mFunctional Data Structures