Algorithms for Trees - Foldable, Applicative, Traversable
summary
Proposes concrete C++ type‑class APIs (functor, foldable, applicative, traversable, monoid) with variable‑template lookup and static dispatch, shows working adapters for four tree shapes (fixed‑point, shared‑ptr binary, fringe, finger tree) and test suites, and claims full implementations are feasible with C++23/26. Demonstrates traversable preserves shape (commuting containers, e.g. range of senders → sender of range, zip‑list/SIMD zipping), measured trees for log‑time split/search, and finger tree use for persistent ropes/text editing.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 1:27Foldable pattern limits
- 6:01Applicative practical uses
- 7:28Traversable generalization
- 13:12Shape-preserving operations
- 13:34Visitors vs pattern matching
- 16:51Type class pattern for C++
- 20:27Recursion schemes
- 27:00Functors minimal interface
- 39:02Foldable vs Traversable
- 42:13Monoids for fold operations
- 45:29Applicative parallel ops
- 51:02Traversable commuting containers
- 57:22Monoids for efficient queries
- 1:09:15Finger trees
- 1:13:55Internal iteration APIs
- 1:24:28Naming conventions
- 1:29:06Extending to monads
related talks
58mMonoids, Monads, and Applicative Functors: Repeated Software Patterns
05mBeautiful Folds
56mAn introduction to recursion schemes
10mFunctional Data Structures
01h 47mFunctional C++
32mFunctional implementation of Finger Trees in JavaScript
01h 04mFunctional C++ For Fun And Profit
38mRefactoring Recursion