Richard Bird takes a radically new approach to algorithm design, namely, design by calculation. These 30 short chapters each deal with a particular programming problem drawn from sources as diverse as games and puzzles, intriguing combinatorial tasks, and more familiar areas such as data compression and string matching. Each pearl starts with the statement of the problem expressed using the functional programming language Haskell, a powerful yet succinct language for capturing algorithmic ideas clearly and simply. The novel aspect of the book is that each solution is calculated from an initial formulation of the problem in Haskell by appealing to the laws of functional programming. Pearls of Functional Algorithm Design will appeal to the aspiring functional programmer, students and teachers interested in the principles of algorithm design, and anyone seeking to master the techniques of reasoning about programs in an equational style.
Author(s): Richard S. Bird
Publisher: Cambridge University Press
Year: 2010
Language: English
Pages: 290
Cover
Half-title
Title
Copyright
Dedication
Content
Preface
1 The smallest free number
Introduction
An array-based solution
A divide and conquer solution
Final remarks
2 A surpassing problem
Introduction
Specification
Divide and conquer
Final remarks
References
3 Improving on saddleback search
Afterword
References
4 A selection problem
Introduction
Formalisation and first steps
Divide and conquer
Final remarks
References
5 Sorting pairwise sums
Introduction
Lambert’s algorithm
Divide and conquer
Final remarks
References
6 Making a century
Introduction
A little theory
Making a century
Final remarks
References
7 Building a tree with minimum height
Introduction
First steps
Fusion
Optimal insertion
Final remarks
References
8 Unravelling greedy algorithms
Introduction
Specification
Derivation
Final remarks
References
9 Finding celebrities
Afterword
References
10 Removing duplicates
Introduction
A first version
A generalisation
Introducing sets
Final remarks
References
11 Not the maximum segment sum
Introduction
Specification
Derivation
Final remarks
References
12 Ranking suffixes
Introduction
Specification
Properties of rank
A better algorithm
Proof
A better rank
The final algorithm
Analysis
Experimental results
Final remarks
References
13 The Burrows—Wheeler transform
Introduction
Defining the BWT
Recreational calculation
A faster algorithm
Transform revisited
Final remarks
References
14 The last tail
Introduction
An inductive definition
Borders
Border
Cocktail
Reducing the problem size
Final optimisations
Final remarks
References
15 All the common prefixes
Introduction
A key property
Dara Refinement
Final remarks
References
16 The Boyer--Moore algorithm
Introduction
The scan lemma
The Boyer-Moore algorithm
Shifting
A final improvement
Computing shifts
Final remarks
References
17 The Knuth–Morris–Pratt algorithm
Introduction
First steps
Data refinement
Trees
Final remarks
References
18 Planning solves the Rush Hour problem
Introduction
Puzzles
Planning
Rush Hour
Results
Final remarks
References
19 A simple Sudoku solver
Introduction
Specification
Pruning the matrix of choices
Single-cell expansion
Final remarks
20 The Countdown problem
Introduction
A simple program
Two optimisations
An even stronger logality test
Memoisation
Skeleton trees
A further experiment
Final remarks
References
21 Hylomorphisms and nexuses
Introduction
Folds, unfolds and hylomorphisms
Three examples
Building a nexus
Why build the nexus?
Final remarks
References
22 Three ways of computing determinants
Introduction
The school-book method
Using rational division
Using integer division
Interleaving
Using no division
A brief comparison
Final remarks
References
23 Inside the convex hull
Introduction
Background
Convex hulls
An incremental algorithm
Finding a simplex
Updates
An inprovement
QuickCheck
Final remarks
References
24 Rational arithmetic coding
Introduction
Arithematic coding with rational arithemetic
Narrowing
Models
Encoding
Decoding
Incremental encoding and decoding
Streaming
Final remarks
References
Appendix
25 Integer arithmetic coding
Introduction
New definitions
Incremental encoding and interval expansion
Interval expansion
A new difinition
A crucial question
A final problem
Inverting streams
The helper function
Incremental decoding
Final remarks
Appendix
26 The Schorr–Waite algorithm
Introduction
Specification
Safe replacement
Eliminating duplicate entries
Threading the stack
Representing the stack by a linked list
Final remarks
References
27 Orderly insertion
Introduction
A naive algorithm
An improved algorithm
Proofs
Implementation
Final remarks
References
28 Loopless functional algorithms
Introduction
Loopless algorithms
Four warm-up exercises
Boustrophedon product
Tupling
Trees and queues
Final remarks
References
29 The Johnson–Trotter algorithm
Introduction
A recursive formulation
The plan
A loopless algorithm
Final remarks
References
30 Spider spinning for dummies
Introduction
A loopless program
Spider spinning with general spiders
A loopless algorithm
Parity spiders
The remaining steps
The initial state
Final remarks
References
Index
