A Helicopter Tour of Purely Functional Data Structures
summary
Walks through concrete implementations and tradeoffs: Scala & Haskell implementations of lists, lazy streams, two‑stack queues, 2‑3 trees and finger trees, plus zippers. Claims and results are specific — queues use a front/rear two‑list trick with amortized O(1) operations and stream memoization to avoid repeated work; finger trees surface the ends for finger trees give amortized O(1) ends and good random access; zippers appear in practice as Circe’s HCursor for efficient nested JSON edits. Code examples compile and illustrate costs and reuse.
AI-written summary · about
chapters (6)
- 0:00Start
- 4:09FUNCTIONAL DEFINITION
- 15:46AMORTIZATION
- 27:03NESTED TYPE STRUCTURE
- 34:38USAGE EXAMPLE
- 37:50CONCLUSION
related talks
41mExotic Functional Data Structures: Hitchhiker Trees
35mChanging the Unchangeable: The Hows and Whys of Immutable Data Structures
24mDesigning Fast and Efficient List-like Data Structures
45mBeyond Lists: High Performance Data Structures
52mData Over Code: A Short Hyperbole
48mC++ Data Structures That Make Video Games Go Round
34mLightweight Relations
45mMost of the Time It Works Every Time: The Mindset Behind Using Probabilistic Data Structures