18 State and Equality
18.1 Boxes: A Canonical Mutable Structure
18.2 Mutation and Types
18.3 Mutation and Equality
18.4 Another Equality Predicate
18.5 A Hierarchy of Equality
18.6 Space and Time Complexity
18.7 What it Means to be Identical
18.8 Comparing Functions
19 Recursion and Cycles from Mutation
19.1 Partial Definitions
19.2 Recursive Functions
19.3 Premature Evaluation
19.4 Cyclic Lists Versus Streams
20 Detecting Cycles
20.1 A Running Example
20.2 Types
20.3 A First Checker
20.4 Complexity
20.5 A Fabulous Improvement
20.6 Testing
21 Avoiding Recomputation by Remembering Answers
21.1 An Interesting Numeric Sequence
21.1.1 Using State to Remember Past Answers
21.1.2 From a Tree of Computation to a DAG
21.1.3 The Complexity of Numbers
21.1.4 Abstracting Memoization
21.2 Edit-Distance for Spelling Correction
21.3 Nature as a Fat-Fingered Typist
21.4 Dynamic Programming
21.4.1 Catalan Numbers with Dynamic Programming
21.4.2 Levenshtein Distance and Dynamic Programming
21.5 Contrasting Memoization and Dynamic Programming
22 Partial Domains
22.1 A Non-Solution
22.2 Exceptions
22.3 The Option Type
22.4 Total Domains, Dynamically
22.5 Total Domains, Statically
22.6 Summary
22.7 A Note on Notation
23 Staging
23.1 Problem Definition
23.2 Initial Solution
23.3 Refactoring
23.4 Separating Parameters
23.5 Context
24 Factoring Numbers
25 Deconstructing Loops
25.1 Setup: Two Functions
25.2 Abstracting a Loop
25.3 Is It Really a Loop?
25.4 Re-Examining for
for
25.5 Rewriting Pollard-Rho
25.6 Nested Loops
25.7 Loops, Values, and Customization