Data Structures of the Dark Side
summary
Explains concrete implementations: a stream zipper positions method that yields every cursor lazily so annotating a “sandwich” element (prev < cur < next) becomes a single coflatMap over cursors and back to stream; shows helper flatMapWids to keep original values. Shows DList encoded as a list -> list function and uses a trampoline for stack-safety so concatenation is O(1). Demonstrates writer-monad logging turning quadratic appends into linear time (example: left-assoc ~8s vs right-assoc ~10ms).
AI-written summary · about
chapters (29)
- 0:00Intro
- 2:19Zippers
- 4:52Choice of Methods
- 6:02Monadic Methods
- 7:51Folds and Catamorphisms
- 9:51Example of Fold
- 12:24Good-Fold Detection
- 14:06Anamorphisms
- 15:03Stream Example
- 18:42Infinite Possibilities
- 22:15Comonads
- 23:41StreamZipper as a Comonad
- 24:12Back to Our Scenario
- 28:00Almost There
- 33:35Unfold for Tree
- 34:02The Writer Monad
- 34:35Example (Root Finding)
- 36:24The Concatenation Problem
- 36:43Benchmarks
- 37:32Recursive Concatenation
- 38:59Naive Implementation
- 40:05Function Composition
- 41:21The Stack Problem
- 42:46Enter Trampolines
- 44:03Adding map
- 44:41Enhancing the Hierarchy
- 45:11Complete Signature
- 46:16Discussion
- 47:26Summary
