Pearls of Functional Algorithm Design

Description

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. 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