Fabulous Adventures in Data Structures and Algorithms

"Rigorous, curious, quietly funny, and extraordinarily generous with hard-won insight."
—Scott Hanselman, Microsoft

This book invites you to step off the beaten path and explore interesting, unfamiliar, and even exotic algorithms that will challenge your perspective and elevate your code. Legendary language designer Eric Lippert guides you with a refreshing, conversational approach, providing beautifully practical examples that highlight the recurring patterns behind stubborn coding problems.

You’ll begin with a fresh look at foundational, thread-safe, and persistent immutable data structures. Lippert demystifies stacks, queues, and finger-tree deques, illustrating how to manage memory efficiently through persistence. For developers working in highly concurrent, cloud native environments, these patterns will help you eliminate hard-to-spot race conditions and state-mutation bugs.

Your fabulous adventure then turns to structural search, compiler design, and the integration of functional programming within mainstream object-oriented languages. You’ll dive into Directed Acyclic Word Graphs (DAWGs), greedy pretty printers, and the complexities of tree unification. This section bridges theory and real-world tools, teaching you how to design highly modular compilers or robust static analysis engines and to write declarative, composable, and expressive APIs.

In the final leg of your journey, you’ll model randomness, statistical reasoning, and continuous probability—core concepts for AI and predictive analytics. Lippert introduces advanced Bayesian and monadic techniques, teaching you how to construct joint distributions and sample them using the powerful Metropolis algorithm. This statistical toolkit aligns perfectly with modern data-driven systems that need to make consistent, sound decisions under real-world uncertainty.

In the age of AI coding, implementation is becoming cheaper. AI can write code, but it cannot relieve developers of responsibility for understanding what the code means, why a given solution was chosen, how it will scale, and whether the problem has been framed correctly. This book develops exactly that judgment. It teaches the part that is becoming more valuable: recognizing, selecting, questioning, and evaluating the ideas behind implementations. It is an apprenticeship in computational taste, taught through unusual and memorable examples.

What's inside

• Build highly efficient, thread-safe concurrent systems using immutable parts
• Compress massive data representation sizes using memoized quadtrees and DAWGs
• Solve complex compiler optimizations using unification and backtracking search
• Automate precise, mathematically sound decisions under real-world uncertainty

About the reader

For working programmers familiar with C#, Java, or Python.

About the author

Eric Lippert has designed programming languages, compilers, and developer tools for Microsoft, Coverity, and Facebook.

Table of Contents

1 Starting a fabulous adventure
Part 1
2 Immutable stacks and queues
3 An immutable deque
4 Memoizing immutable quadtrees to make a better Life
5 What’s up with you, Directed Acyclic Word Graph?
6 Combinatorial algorithms
7 First abstract nonsense interlude: Category theory
Part 2
8 Coloring graphs with backtracking search
9 Greedy iterative pretty printing
10 Unification and anti-unification
11 Second abstract nonsense interlude: Monads
Part 3
12 A better abstraction for randomness
13 Conditional probability with Bayes’ theorem
14 Third abstract nonsense interlude: The probability monad
15 Sampling continuous distributions
16 Markov processes and the Metropolis algorithm
A Notes on C#
B Further reading