Pearls of Functional Algorithm Design

Front Cover
Cambridge University Press, Sep 16, 2010 - Computers
0 Reviews
Richard Bird takes a radical 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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

1 The smallest free number
1
2 A surpassing problem
7
3 Improving on saddleback search
12
4 A selection problem
21
5 Sorting pairwise sums
27
6 Making a century
33
7 Building a tree with minimum height
41
8 Unravelling greedy algorithms
50
17 The KnuthMorrisPratt algorithm
127
18 Planning solves the Rush Hour problem
136
19 A simple Sudoku solver
147
20 The Countdown problem
156
21 Hylomorphisms and nexuses
168
22 Three ways of computing determinants
180
23 Inside the convex hull
188
24 Rational arithmetic coding
198

9 Finding celebrities
56
10 Removing duplicates
64
11 Not the maximum segment sum
73
12 Ranking suffixes
79
13 The BurrowsWheeler transform
91
14 The last tail
102
15 All the common prefixes
112
16 The BoyerMoore algorithm
117
25 Integer arithmetic coding
208
26 The SchorrWaite algorithm
221
27 Orderly insertion
231
28 Loopless functional algorithms
242
29 The JohnsonTrotter algorithm
251
30 Spider spinning for dummies
258
Index
275
Copyright

Other editions - View all

Common terms and phrases

About the author (2010)

Richard Bird is Professor of Computer Science at Oxford University Computing Laboratory.

Bibliographic information