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.
Author(s): John David Stone
Publisher: Springer
Year: 2018
Language: English
Pages: 395
City: 2018
Tags: algorithms,scheme
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
