Algorithms for Functional Programming

This book presents a variety of widely used algorithms, expressing them in a pure functional programming language to make their structure and operation clearer to readers. In the opening chapter the author introduces the specific notations that constitute the variant of Scheme that he uses. The second chapter introduces many of the simpler and more general patterns available in functional programming. The chapters that follow introduce and explain data structures, sorting, combinatorial constructions, graphs, and sublist search. Throughout the book the author presents the algorithms in a purely functional version of the Scheme programming language, which he makes available on his website. The book is supported with exercises, and it is suitable for undergraduate and graduate courses on programming techniques. Preface Acknowledgements Contents Chapter 1 Essential Notations 1.1 Simple Values Exercises 1.2 Identifiers and Expressions Exercises 1.3 Functions and Procedures 1.4 Arithmetic Functions Addition Subtraction Multiplication Division Exponentiation Procedure Summaries Exercises 1.5 Procedure Calls Exercises 1.6 lambda-Expressions Procedures of Variable Arity Building Lists Returning Multiple Values Computations Without Results Exercises 1.7 Predicates Classification Predicates Equality Predicates Equality and Types Exercises 1.8 Conditional Expressions and-Expressions and or-Expressions Exercises 1.9 Definitions Procedure Definitions Recursive Definitions Exercises 1.10 Local Bindings Local Procedures Local Recursion Expressions Exercises Chapter 2 The Tool Box 2.1 List Mapping The map Procedure Exercises 2.2 Constant Procedures Exercises 2.3 Procedure Sections The invoke Procedure Currying Exercises 2.4 Couplers Procedure Composition Parallel Application Dispatching Exercises 2.5 Adapters Selection Rearrangement Preprocessing and Postprocessing Exercises 2.6 Recursion Managers The recur Procedure Recursive Predicates Iteration Exercises 2.7 Euclid’s Algorithm Exercises 2.8 Raised Boolean Procedures Operating on Booleans and on Predicates The ^if Procedure Exercises 2.9 Natural Numbers and Recursion Mathematical Induction Managing Recursion with Natural Numbers Tallying Bounded Generalization Exercises Chapter 3 Data Structures 3.1 Modeling Exercises 3.2 The Null Value Exercises 3.3 Sum Types Enumerations Discriminated Union Recursive Type Equations Exercises 3.4 Pairs Naming Pairs Product Types Discriminated Unions Reconsidered Reimplementing Natural Numbers Exercises 3.5 Boxes Using Pairs to Model Boxes Exercises 3.6 Lists Selection Procedures Homogeneous Lists Recursive Procedures for Lists The Principle of List Induction Managing Recursion with Lists Unfolding Exercises 3.7 List Algorithms Arity Extension Filtering and Partitioning Sublists Positional Selection Extending Predicates from List Elements to Lists Transposing, Zipping, and Unzipping Aggregating Multiple Results Exercises 3.8 Sources Finite Sources Exercises 3.9 Tuples Building the Model Record Types Exercises 3.10 Trees The Principle of Tree Induction Managing Recursion with Trees Exercises 3.11 Bushes The Principle of Bush Induction Managing Recursion with Bushes Exercises 3.12 Bags Basic Bag Procedures Bag Operations Managing Recursion with Bags Exercises 3.13 Equivalence Relations Extending Equivalence Relations Exercises 3.14 Sets Managing Recursion with Sets Filtering and Partitioning Sets Additional Set Operations Union, Intersection, and Difference Exercises 3.15 Tables Updating Tables Exercises 3.16 Buffers Managing Recursion with Buffers Exercises Chapter 4 Sorting 4.1 Ordering Relations Implicitly Defined Equivalence Relations Testing Whether a List Is Ordered Searching for an Extreme Value Compound Ordering Relations Lexicographic Ordering Exercises 4.2 Sorting Algorithms Sorting by Insertion Sorting by Selection Quicksort Sorting by Merging Exercises 4.3 Binary-Search Trees Testing the Binary-Search-Tree Invariant Extracting a Value from a Binary-Search Tree Binary-Search-Tree Sort Exercises 4.4 Red-Black Trees Implementing Red-Black Trees Color Flips and Rotations Insertion Search Deletion Implementing Tables with Red-Black Trees Exercises 4.5 Heaps Folding and Unfolding Heaps Heap Sort Exercises 4.6 Order Statistics Exercises Chapter 5 Combinatorial Constructions 5.1 Cartesian Products Ordering Cartesian Products Ranking and Unranking Exercises 5.2 List Selections Sublists Sections Subsequences and Selections Exercises 5.3 Bag Selections Exercises 5.4 Permutations Ranking and Unranking Exercises 5.5 Partitions Bag Partitions Partitioning Natural Numbers Exercises Chapter 6 Graphs 6.1 Implementing Graphs Graph Construction Graphs and Relations Properties of Graphs Additional Graph Accessors Undirected Graphs Exercises 6.2 Depth-First Traversal Traversing Graphs The Depth-First Order Topological Sorting Reachable Vertices Exercises 6.3 Paths Connected Components Exercises 6.4 Breadth-First Traversal Exercises 6.5 Spanning Trees An Alternative Method Exercises 6.6 Shortest Paths The Bellman–Ford Algorithm Dijkstra’s Algorithm The Floyd–Warshall Algorithm Exercises 6.7 Flow Networks Residual Networks and Maximum Flows Exercises Chapter 7 Sublist Search 7.1 The Simple, Slow Algorithm Substring Search Exercises 7.2 The Knuth–Morris–Pratt Algorithm Substring Search Exercises 7.3 The Boyer–Moore Algorithm Exercises 7.4 The Rabin–Karp Algorithm Exercises Appendix A Recommended Reading Appendix B The (afp primitives) Library Appendix C Using the AFP Libraries Scheme Language Processors Downloading and Installing the Libraries Creating Program Files Executing Programs Limitations Index This book presents a variety of widely used algorithms, expressing them in a pure functional programming language to make their structure and operation clearer to readers. The opening chapter explains the key functional programming principles. In functional programming, sometimes a pattern of adaptation and combination appears repeatedly, the second chapter introduces many of the simpler and more general patterns. The chapters that follow explain data structures, sorting, combinatorial constructions, graphs, and sublist search. The author presents the algorithms in a purely functional version of the Scheme programming language, which he makes available on his website. The book is supported throughout with exercises, and it is suitable for graduate-level courses on programming techniques