Extreme Cleverness: Functional Data Structures in Scala
summary
Implements six persistent structures in Scala with working code on GitHub and concrete performance claims: singly linked lists with structural sharing for O(1) head, Banker's queues with amortized O(1) enqueue/dequeue, red‑black trees for O(log n) associative ops, two‑three finger trees that offer amortized O(1) ends but are “ridiculously slow” in practice, and a bitmapped vector trie (Vector) with log32 n ≈ 7 depth requiring at most 7 array derefs and 14 bit ops, and measured ~2–2.5× slower than java.util.ArrayList. JVM cache locality dominates real performance.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:20Overview
- 3:05Functional Data Structures
- 4:44Sequential Data Structures
- 8:28Bankers Queue
- 9:49Bakers Queue
- 15:03Double Ended Queue
- 20:34Complexity bounds
- 21:06Balanced binary search
- 22:49Balanced red black tree
- 27:24Complex bounds
- 30:54Case
- 34:07locality of reference
- 38:24References
related talks
54mHow Not to Write Slow Scala
28mRust and Scala, Sitting in a Tree….
48mHigh performance Scala systems without tears
42mWhat Scala can learn from Rust, Swift, and C++
31mDESIGNING DATA STRUCTURES FOR THE TYPELEVEL ECOSYSTEM
49mNumbers every Scala programmer should know
23mThe Future of Scala Performance on Big Data
28mArrayDeques and How to Contribute to Scala 2.13 Collections