Purely Dysfunctional Data Structures

on YouTube ↗47m

" summary

Explains why efficient immutable collections need structural sharing rather than naive copying, shows concrete pitfalls (String substring and ArrayList subList share backing arrays and cause surprises), describes persistent linked lists, the two-list (banker) queue and its amortized costs, and the Hash Array Mapped Trie (wide branching like 32 yields ~6–7 hops even for huge maps). Notes immutability doesn’t remove concurrency work, costs more memory but benefits from GC, and recommends the Vavr library as a practical Java option.

AI-written summary · about

" chapters (19)

1. 0:00Introduction to immutability
2. 2:41Problems with mutable abstractions
3. 5:55Benefits of immutability
4. 7:44Definition of immutable objects
5. 10:35Practical immutability limits
6. 12:04Designing immutable APIs
7. 15:14Persistent data structures
8. 17:44Real-world immutability challenges
9. 21:57Immutable linked list basics
10. 24:22Thread safety with immutable data
11. 26:50Concurrency trade-offs
12. 28:39Immutable set implementation
13. 31:15Persistent queue solutions
14. 33:41Performance of persistent queues
15. 36:13Cache efficiency in data structures
16. 38:41Persistent hash map attempts
17. 43:36Complexity of immutability
18. 44:39Key takeaways and libraries
19. 46:05Conclusion and resources

" related talks

• 48mPurely Functional Data StructuresGrzegorz Piwowarek · GeeCON 2019
• 48mFunctional data structures in JavaOleg Šelajev · Voxxed Days Zurich 2017
• 48mPurely functional data structures demystifiedMohit Thatte · Functional Conf 2014
• 01h 00mImmutable Data with Java: Using Immutable Data StructuresManuel Mauky · W-JAX 2018
• 42mPure Functions and Immutable ObjectsVictor Rentea · Devnexus 2021
• 02h 27mEscape from the Planet of the CollectionsMaurice Naftalin, Stuart Marks · Devoxx Belgium 2024
• 34mFunctional Programming Anti-Patterns in JavaVictor Rentea · XtremeJ 2023
• 01h 01mFunctional C++Kevlin Henney · NDC London 2017