What this book covers
Chapter 1, Why Functional Programming?, takes you on a whirlwind tour of the functional programming (FP) paradigm. We try to highlight the many advantages FP brings to the table when compared with the imperative programming paradigm. We discuss FP’s higher level of abstraction, being declarative, and reduced boilerplate. We talk about the problem of reasoning about the state change. We see how being immutable helps realize "an easier to reason about system".
Chapter 2, Building Blocks, provides a whirlwind tour of basic concepts in algorithms. We talk about the Big O notation for measuring algorithm efficiency. We discuss the space time trade-off apparent in many algorithms. We next look at referential transparency, a functional programming concept. We will also introduce you to the notion of persistent data structures.
Chapter 3, Lists, looks at how lists are implemented in a functional setting. We discuss the concept of persistent data structures in depth here, showing how efficient functional algorithms try to minimize copying and maximize structural sharing.
Chapter 4, Binary Trees, discusses binary trees. We look at the traditional binary tree algorithms, and then look at Binary Search Trees.
Chapter 5, More List Algorithms, shows how the prepend operation of lists is at the heart of many algorithms. Using lists to represent binary numbers helps us see what lists are good at. We also look at greedy and backtracking algorithms, with lists at the heart.
Chapter 6, Graph Algorithms, looks at some common graph algorithms. We look at graph traversal and topological sorting, an important algorithm for ordering dependencies.
Chapter 7, Random Access Lists, looks at how we could exploit Binary Search Trees to access a random list element faster.
Chapter 8, Queues, looks at First In First Out (FIFO) queues. This is another fundamental data structure. We look at some innovative uses of lists to implement queues.
Chapter 9, Streams, Laziness, and Algorithms, looks at lazy evaluation, another FP feature. This is an important building block for upcoming algorithms, so we refresh ourselves with some deferred evaluation concepts.
Chapter 10, Being Lazy – Queues and Deques, looks at double-ended queues, which allow insertion and deletion at both ends. We first look at the concept of amortization. We use lazy lists to improve the queue implementation presented earlier, in amortized constant time. We implement deques also using similar techniques.
Chapter 11, Red-Black Trees, shows how balancing helps avoid degenerate Binary Search Trees. This is a comparatively complex data structure, so we discuss each algorithm in detail.
Chapter 12, Binomial Heaps, covers heap implementation offering very efficient merge operation. We implement this data structure in a functional setting.
Chapter 13, Sorting, talks about typical functional sorting algorithms.