Algorithms for Functional Programming

Description

Preface......Page 3 Contents......Page 6 Simple Values......Page 9 Identifiers and Expressions......Page 12 Exercises......Page 13 Functions and Procedures......Page 14 Addition......Page 15 Division......Page 16 Procedure Summaries......Page 18 Exercises......Page 20 Procedure Calls......Page 21 lambda-Expressions......Page 22 Procedures of Variable Arity......Page 24 Building Lists......Page 26 Returning Multiple Values......Page 27 Computations Without Results......Page 28 Exercises......Page 29 Predicates......Page 30 Equality and Types......Page 31 Conditional Expressions......Page 34 and-Expressions andor-Expressions......Page 36 Definitions......Page 37 Procedure Definitions......Page 38 Recursive Definitions......Page 39 Exercises......Page 40 Local Bindings......Page 41 Local Recursion......Page 42 receive-Expressions......Page 44 Exercises......Page 46 The map Procedure......Page 47 Exercises......Page 48 Constant Procedures......Page 49 Procedure Sections......Page 51 TheinvokeProcedure......Page 52 Currying......Page 53 Exercises......Page 54 Procedure Composition......Page 55 Parallel Application......Page 56 Dispatching......Page 57 Adapters......Page 58 Selection......Page 59 Rearrangement......Page 60 Preprocessing and Postprocessing......Page 61 Exercises......Page 63 The recurProcedure......Page 64 Recursive Predicates......Page 66 Iteration......Page 67 Euclid’s Algorithm......Page 72 Exercises......Page 75 Operating on Booleans and on Predicates......Page 76 The^ifProcedure......Page 77 Exercises......Page 78 Mathematical Induction......Page 79 Managing Recursion with Natural Numbers......Page 80 Tallying......Page 85 Bounded Generalization......Page 87 Exercises......Page 89 Modeling......Page 90 The Null Value......Page 91 Enumerations......Page 92 Discriminated Union......Page 93 Exercises......Page 95 Pairs......Page 96 Product Types......Page 97 Discriminated Unions Reconsidered......Page 98 Reimplementing Natural Numbers......Page 99 Exercises......Page 101 Using Pairs to Model Boxes......Page 102 Lists......Page 104 Selection Procedures......Page 106 Homogeneous Lists......Page 108 Recursive Procedures for Lists......Page 109 The Principle of List Induction......Page 110 Managing Recursion with Lists......Page 111 Unfolding......Page 114 Arity Extension......Page 120 Filtering and Partitioning......Page 123 Sublists......Page 126 Positional Selection......Page 127 Extending Predicates from List Elements to Lists......Page 128 Transposing, Zipping, and Unzipping......Page 129 Aggregating Multiple Results......Page 131 Exercises......Page 135 Sources......Page 137 Finite Sources......Page 145 Tuples......Page 150 Building the Model......Page 151 Record Types......Page 152 Exercises......Page 153 Trees......Page 154 The Principle of Tree Induction......Page 157 Managing Recursion with Trees......Page 158 Exercises......Page 163 Bushes......Page 165 Managing Recursion with Bushes......Page 167 Bags......Page 171 Basic Bag Procedures......Page 172 Bag Operations......Page 174 Managing Recursion with Bags......Page 175 Exercises......Page 179 Equivalence Relations......Page 180 Extending Equivalence Relations......Page 182 Sets......Page 184 Managing Recursion with Sets......Page 186 Filtering and Partitioning Sets......Page 187 Additional Set Operations......Page 188 Union, Intersection, and Difference......Page 189 Exercises......Page 195 Tables......Page 196 Updating Tables......Page 199 Buffers......Page 203 Managing Recursion with Buffers......Page 206 Exercises......Page 208 Ordering Relations......Page 209 Testing Whether a List Is Ordered......Page 210 Searching for an Extreme Value......Page 211 Compound Ordering Relations......Page 213 Lexicographic Ordering......Page 214 Sorting Algorithms......Page 218 Sorting by Insertion......Page 219 Quicksort......Page 220 Sorting by Merging......Page 221 Binary-Search Trees......Page 224 Testing the Binary-Search-Tree Invariant......Page 225 Extracting a Value from a Binary-Search Tree......Page 227 Binary-Search-Tree Sort......Page 229 Exercises......Page 230 Red-Black Trees......Page 231 Implementing Red-Black Trees......Page 233 Color Flips and Rotations......Page 235 Insertion......Page 236 Deletion......Page 239 Implementing Tables with Red-Black Trees......Page 246 Heaps......Page 255 Folding and Unfolding Heaps......Page 259 Heap Sort......Page 260 Exercises......Page 262 Order Statistics......Page 263 Exercises......Page 265 Cartesian Products......Page 266 Ordering Cartesian Products......Page 269 Ranking and Unranking......Page 270 Sublists......Page 275 Sections......Page 280 Subsequences and Selections......Page 282 Exercises......Page 288 Bag Selections......Page 289 Exercises......Page 290 Permutations......Page 291 Ranking and Unranking......Page 293 Exercises......Page 295 Bag Partitions......Page 296 Partitioning Natural Numbers......Page 298 Exercises......Page 300 Implementing Graphs......Page 301 Graph Construction......Page 303 Graphs and Relations......Page 305 Properties of Graphs......Page 307 Additional Graph Accessors......Page 309 Undirected Graphs......Page 311 Exercises......Page 318 Traversing Graphs......Page 319 The Depth-First Order......Page 320 Topological Sorting......Page 321 Reachable Vertices......Page 322 Exercises......Page 323 Paths......Page 324 Connected Components......Page 325 Breadth-First Traversal......Page 327 Exercises......Page 329 Spanning Trees......Page 330 An Alternative Method......Page 332 Exercises......Page 334 The Bellman–Ford Algorithm......Page 335 Dijkstra’s Algorithm......Page 337 The Floyd–Warshall Algorithm......Page 339 Flow Networks......Page 343 Residual Networks and Maximum Flows......Page 346 Exercises......Page 350 The Simple, Slow Algorithm......Page 351 Substring Search......Page 353 Exercises......Page 354 The Knuth–Morris–Pratt Algorithm......Page 355 Substring Search......Page 361 Exercises......Page 363 The Boyer–Moore Algorithm......Page 364 Exercises......Page 366 The Rabin–Karp Algorithm......Page 367 Exercises......Page 373 Reading......Page 375 afp primitives Library......Page 377 Downloading and Installing the Libraries......Page 380 Creating Program Files......Page 381 Executing Programs......Page 382 Limitations......Page 383 Index......Page 385