Truly Functional Solutions to the Longest Uptrend Problem (Functional Pearl)
summary
Replaces the array-based LIS implementation with purely functional structures, shows a first persistent-sequence version runs about 6× slower, then builds a practical solution using Huet's zipper, red‑black trees and a left‑spine/finger‑tree view so binary search becomes exponential search on the spine. Benchmarks show red‑black and left‑spine implementations match the imperative runtime in practice, and the finger‑tree variant gains adaptive linear behaviour on nearly‑sorted inputs, with code and artifacts available.
AI-written summary · about
chapters (11)
- 0:00Functional solutions intro
- 1:25Imperative to functional
- 5:23Integer indices problem
- 6:10Zippers for position
- 7:58Binary search with zippers
- 11:20Longest uptrend with zippers
- 13:53Degenerate tree fix
- 16:47Red-black tree spine
- 19:19Finger trees and search
- 20:02Benchmark results
- 21:52Conclusion
related talks
48mFunctional data structures in Java
32mFunctional implementation of Finger Trees in JavaScript
48mPurely Functional Data Structures
01h 04mFunctional C++ For Fun And Profit
36mConcrete Functional Programming
47mPurely Dysfunctional Data Structures
01h 06mDesigning Applications with Functional Programming Constructs
51mFunctional Programming with Java