Purely Functional Data Structures
summary
Persistent immutable collections minimize copying by structural sharing and often match mutable performance with clever designs. Practical examples: a singly linked list gives O(1) prepend but O(n) append; the bankers queue (two-list) yields amortized O(1) enqueue/dequeue but occasional O(n) reversals; a Hash Array Mapped Trie (HAMT) uses 32-way branching to keep lookup depth ≈6 hops so lookups are fast and memory is kept down with bitmaps. Real trade-offs: GC pressure (authors report ~1 GB/s garbage), cache locality, and central contention versus fine-grained locking in mutable concurrent maps.
AI-written summary · about
chapters (24)
- 0:00Introduction
- 1:17Immutability trends and costs
- 4:16Benefits of immutability
- 7:06Defining immutability
- 9:17Thread safety and immutability
- 10:20Designing immutable APIs
- 13:11Persistent data structures
- 15:44The unicorn myth
- 16:28String and substring optimizations
- 18:56Designing persistent classes
- 19:18Persistent linked lists
- 21:47Thread safety with persistent structures
- 23:54Concurrency trade-offs
- 26:02Persistent sets and trees
- 27:48Persistent queues
- 30:39Finger trees for queues
- 33:55Persistent maps and tries
- 36:50Hash array mapped tries
- 39:06Time complexity of tries
- 41:14Trade-offs in persistence
- 42:16Key to efficiency
- 43:39Choosing between mutable and immutable
- 44:00Further reading and research
- 45:03Q&A session
related talks
47mPurely Dysfunctional Data Structures
48mFunctional data structures in Java
48mPurely functional data structures demystified
42mPure Functions and Immutable Objects
36mConcrete Functional Programming
01h 04mFunctional C++ For Fun And Profit
34mImmutability: Putting The Dream Machine To Work
01h 01mFunctional C++