Functional data structures in Java
summary
Claims that functional data structures are immutable and persistent and still practical by reusing structure, using lazy evaluation, and applying amortized analysis. Implements cons lists, a two-list queue with amortized O(1) enqueue/dequeue via occasional reversals, hash-array-mapped tries for maps, and zippers for local tree updates. Uses Java 8 libraries such as JavaSlang (and mentions PCollections), runs JMH microbenchmarks showing functional priority queues are somewhat slower than mutable ones but within a constant factor, and cites Okasaki’s book as the reference.
AI-written summary · about
chapters (21)
- 0:00Intro
- 1:34REVOLUTIONARY DEVELOPER TOOLS
- 2:03WHAT DOES FUNCTIONAL MEAN?
- 7:34MUTABLE DATA STRUCTURES
- 10:44PERSISTENT DATA STRUCTURES
- 15:51HOW TO PREPEND A LIST
- 18:29HOW TO APPEND TO A LIST
- 18:59ALGORITHMIC COMPLEXITY
- 20:17AMORTIZED COMPLEXITY
- 22:02BANKER'S METHOD
- 25:01HOW TO BUILD A QUEUE
- 28:47HOW TO TAIL A QUEUE
- 29:09HOW TO PEEK
- 29:48HOW TO DEQUEUE
- 33:29ISN'T REVERSE EXPENSIVE?
- 34:30HOW TO BUILD A MAP
- 37:03UPDATING THE MAP
- 38:12NORMAL TREES
- 42:06BENCHMARKS
- 44:07RESULTS (SAFE HARBOR)
- 45:46Purely functional Data Structures
related talks
47mPurely Dysfunctional Data Structures
48mPurely Functional Data Structures
51mFunctional Programming with Java
48mPurely functional data structures demystified
46mDesigning Functional Programs
36mConcrete Functional Programming
48mEmbrace the Func - How Far has Functional Programming Come in Java?
52mFunctional Programming with Java 8