Pearls of Functional Algorithm Design.pdf

(1434 KB) Pobierz

This page intentionally left blank

P E A R L S O F F U N C T I O NA L A L G O R I T H M D E S I G N

Pearls of Functional Algorithm Design

Richard Bird takes a radically new

approach to algorithm design, namely design by calculation. The body of the text

is divided into 30 short chapters, called pearls, each of which deals with a partic-

ular programming problem. These problems, some of which are completely new,

are drawn from sources as diverse as games and puzzles, intriguing combinatorial

tasks and more familiar algorithms in 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 the problem statement 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.

ICHARD

IRD

is Professor of Computer Science at Oxford University and Fellow

of Lincoln College, Oxford.

P EA R LS O F FUNCT IONAL

AL G ORI T HM DE SIGN

RICHARD BIRD

University of Oxford