Data Structures of the Dark Side

Explore advanced data structures and functional programming concepts in this 50-minute conference talk from Scala Days New York 2016. Dive into unfamiliar yet useful structures like DList (Difference List) and Zippers, examining their use cases, advantages, and disadvantages. Learn about implementation techniques and related topics including Anamorphisms, Trampolines, the Writer monad, and Co-Monads. Follow along as the speaker covers various methods, folds, catamorphisms, infinite possibilities, and practical examples such as root finding. Discover solutions to common problems like concatenation and stack overflow through recursive techniques, function composition, and the use of trampolines. Gain insights into enhancing data structure hierarchies and implementing complete signatures for more efficient functional programming in Scala.

Intro
Zippers
Choice of Methods
Monadic Methods
Folds and Catamorphisms
Example of Fold
Good-Fold Detection
Anamorphisms
Stream Example
Infinite Possibilities
Comonads
StreamZipper as a Comonad
Back to Our Scenario
Almost There
Unfold for Tree
The Writer Monad
Example (Root Finding)
The Concatenation Problem
Benchmarks
Recursive Concatenation
Naive Implementation
Function Composition
The Stack Problem
Enter Trampolines
The Trampoline Data Type
Adding map
Enhancing the Hierarchy
Complete Signature
Discussion
Summary