Learning Functional Data Structures and Algorithms

Description

Contents......Page 3 Preface......Page 8 Why Functional Programming......Page 15 The imperative way......Page 16 Higher level of abstraction......Page 17 Functional programming is declarative......Page 20 No boilerplate......Page 21 Higher order functions......Page 23 Controlling state changes......Page 26 Recursion aids immutability......Page 28 Copy-on-write......Page 30 Laziness and deferred execution......Page 31 Composing functions......Page 33 Summary......Page 36 The Big O notation......Page 37 Space/time trade-off......Page 40 Referential transparency......Page 47 Vectors versus lists......Page 49 Complexities and collections......Page 55 Summary......Page 62 Lists......Page 63 First steps......Page 64 List head and tail......Page 68 Drop elements......Page 71 Concatenating lists......Page 73 Persistent data structures......Page 76 Tail call optimization......Page 77 List append......Page 79 List prepend......Page 81 Getting value at index......Page 83 Modifying a list value......Page 85 Summary......Page 87 Binary Trees......Page 88 Node definitions......Page 89 Building the tree......Page 91 Comparing trees......Page 96 The accumulator idiom......Page 102 Binary Search Trees......Page 105 Exercising it......Page 109 Summary......Page 110 Binary numbers......Page 111 Greedy algorithms and backtracking......Page 120 Summary......Page 126 Graph Algorithms......Page 127 Reversing a list......Page 128 Graph algorithms......Page 130 Cycle detection......Page 139 Summary......Page 141 Random Access Lists......Page 143 Incrementing a binary number......Page 144 List of tree roots......Page 147 Summary......Page 159 Queues......Page 161 Understanding FIFO queues......Page 162 Functional FIFO queues......Page 163 Invariants......Page 165 Implementing a priority queue......Page 166 Understanding priority queues/heaps......Page 168 Leftist trees......Page 171 Functional heaps......Page 173 Summary......Page 180 Streams, Laziness & Algorithms......Page 182 Program evaluation......Page 183 Argument evaluation......Page 185 Memoization – remembering past results......Page 193 Streams......Page 199 Some algorithms on stream......Page 208 Summary......Page 215 Being Lazy - Queues & Deques......Page 216 Imperative implementations......Page 218 Amortization......Page 219 Problem with queues......Page 220 Strict versus lazy......Page 221 Streams......Page 222 Streams meet queues......Page 224 A sense of balance......Page 227 Amortized deques......Page 228 Summary......Page 232 Red-Black Trees......Page 234 Terminology......Page 235 The concept of rotation......Page 236 Red-Black trees......Page 238 Inserting a node......Page 241 Verifying the transformation......Page 251 Complexity......Page 252 Summary......Page 253 Binomial Heaps......Page 254 Binomial trees......Page 256 A binomial heap......Page 260 Binary number equivalence......Page 266 Summary......Page 272 Sorting......Page 273 Stable and unstable sorting......Page 274 Bubble sort......Page 276 Selection sort......Page 281 Insertion sort......Page 285 Merge sort......Page 289 Quick sort......Page 296 Summary......Page 300 Index......Page 301