19 State and Equality
19.1 Boxes: A Canonical Mutable Structure
19.2 Mutation and Types
19.3 Mutation and Equality
19.4 Another Equality Predicate
19.5 A Hierarchy of Equality
19.6 Space and Time Complexity
19.7 What it Means to be Identical
19.8 Comparing Functions
20 Recursion and Cycles from Mutation
20.1 Partial Definitions
20.2 Recursive Functions
20.3 Premature Evaluation
20.4 Cyclic Lists Versus Streams
21 Detecting Cycles
21.1 A Running Example
21.2 Types
21.3 A First Checker
21.4 Complexity
21.5 A Fabulous Improvement
21.6 Testing
22 Avoiding Recomputation by Remembering Answers
22.1 An Interesting Numeric Sequence
22.1.1 Using State to Remember Past Answers
22.1.2 From a Tree of Computation to a DAG
22.1.3 The Complexity of Numbers
22.1.4 Abstracting Memoization
22.2 Edit-Distance for Spelling Correction
22.3 Nature as a Fat-Fingered Typist
22.4 Dynamic Programming
22.4.1 Catalan Numbers with Dynamic Programming
22.4.2 Levenshtein Distance and Dynamic Programming
22.5 Contrasting Memoization and Dynamic Programming
23 Partial Domains
23.1 A Non-Solution
23.2 Exceptions
23.3 The Option Type
23.4 Total Domains, Dynamically
23.5 Total Domains, Statically
23.6 Summary
23.7 A Note on Notation
24 Staging
24.1 Problem Definition
24.2 Initial Solution
24.3 Refactoring
24.4 Separating Parameters
24.5 Context
25 Factoring Numbers
26 Deconstructing Loops
26.1 Setup: Two Functions
26.2 Abstracting a Loop
26.3 Is It Really a Loop?
26.4 Re-Examining for
for
26.5 Rewriting Pollard-Rho
26.6 Nested Loops
26.7 Loops, Values, and Customization