What do you think?
Rate this book
Pearls of Functional Algorithm Design
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.
290 pages, Hardcover
First published September 16, 2010
36 people are currently reading
1123 people want to read
About the author
Richard S. Bird
8 books16 followersProf. Richard Simpson Bird is a computer scientist.
There are other authors named Richard Bird:
* Richard Bird — a horticultural expert and gardening author
* Richard Bird — a contemporary author
* Richard Bird — an early 20th-century author
There are other authors named Richard Bird:
* Richard Bird — a horticultural expert and gardening author
* Richard Bird — a contemporary author
* Richard Bird — an early 20th-century author
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 5 of 5 reviews
April 13, 2019
The book is full of challenging content and enlightening discussions.
As any Bird book, it's packed with useful information, making for an enriching read, albeit hard to follow at times.
I feel the author could have done more justice to some pearls by providing more examples and drawings to help the reader follow along, for example, on the convex hull pearl, or pearls 15 to 17 (those dealing with common prefixes, Boyer-Moore and Knuth-Morris-Pratt). Thus, one has to really take time and digest the contents to make the most of it.
Nonetheless, the wide arrange of topics treated, and the way the author reasons to derive efficient programs from clear, simple specifications is a delight.
Particularly mindboggling was when, while deriving the Boyer-Moore algorithm, simply stating an equation in a different way allows deriving KMP.
The pearls tend to be just a couple pages long, and Bird manages to accompany the rigorous presentations, with laid back discussions and humor when appropriate.
Highly recommended, specially when having read some of his other functional programming books and looking for more.
As any Bird book, it's packed with useful information, making for an enriching read, albeit hard to follow at times.
I feel the author could have done more justice to some pearls by providing more examples and drawings to help the reader follow along, for example, on the convex hull pearl, or pearls 15 to 17 (those dealing with common prefixes, Boyer-Moore and Knuth-Morris-Pratt). Thus, one has to really take time and digest the contents to make the most of it.
Nonetheless, the wide arrange of topics treated, and the way the author reasons to derive efficient programs from clear, simple specifications is a delight.
Particularly mindboggling was when, while deriving the Boyer-Moore algorithm, simply stating an equation in a different way allows deriving KMP.
The pearls tend to be just a couple pages long, and Bird manages to accompany the rigorous presentations, with laid back discussions and humor when appropriate.
Highly recommended, specially when having read some of his other functional programming books and looking for more.
December 25, 2015
Nah. No motivation, no derivations, just some guy showing how smart he is at irrelevant functional algorithms.
June 15, 2025
This is one of the rare occasions where after reading several chapters I decided to stop reading the book because I spent a ton of time reading it and the ratio of value extracted vs. time spent was so bad I decided to give 1-star.
Let me describe the chapter 2 - Surpassing problem as an example.
At the beginning Bird outlines a function from which he wishes to derive a solution (so far so good).
But then out of the blue introduces "divide and conquer property of tails" that "we will need". Right off the bat it's impossible to derive the solution from first principles, because Bird already introduced deus ex machina code he uses to get his solution. How he came to the conclusion "we will need" this property we will never know.
From this property the author derives a 'join' function.
Unfortunately in multiple steps of the derivation he does "magical" code re-writes. One where he says he just does "operator distribution" but in fact
also changes another part of code substantially. In another Bird adds an unexpected substitution "ys = map fst (table ys)". These derivations feel "magical" because you have no idea why the author does them. You need to trace things from end to the beginning for them to make sense.
In another derivation Bird introduces dropWhile which assumes input of a function is
sorted, but this was very suprising to me. Only 2 sentences after dropWhile is introduced the author says input must be sorted and adds "sort". I learned something useful from this for the next chapters of the book - if you don't understand something keep reading!
Then there is a passage where he writes a new function that does a "reduction" from functions"2.2" and "2.3", but in fact there is nothing of value added except the use of variables from synonyms an also it's unclear what is being "reduced" since this new join definition is now 2x longer than the previous one ("2.2") and harder to read. This new join is also never used. Maybe there was some deeper thought but it's just lost on me.
At the end of the chapter the author says "... and tcount x tys = tcount x tys' by (2.1), ...", you of course go to 2.1 and you see "tcount z tys = length (dropWhile((z ≥) · fst) tys)" and you are like why are they equal? Is it because "tys" is sorted or because "≥" or some other explanation?
Ironically several parts of the chapter were dedicated to deriving and optimizing "tcount" function which at the end Bird shows we didn't need at all and could derive the computation by simple though process, all you needed was length of a list.
Another thing that adds to the frustration is that Bird also repeats some definitions, for example 'join' function in this chapter, but changes variable names so if you get used to 'z' meaning something in the next passage it is replaced by 'x'. Also sometimes he gives function definitions with function names and sometimes without.
Last point I'd like to make is that chapter 2 is only 4 pages long (yes four pages!) and it took me 2+ hours to read. If I would be given the test to implement the "Surpassing problem" on my own I could not replicate the solution from Birds book because multiple steps are not intuitive to me and the end solution does not resemble what the chapter was building up to (imho).
If I'd skip the whole chapter and just analyze and play with the solution presented at the end of the chapter in ghci I would get much more out of it than reading and re-reading the chapter.
The other chapters I've read are variations on chapter 2. For example in the next chapter which searches an inverse of "f (x , y) = z" it says "You can assume that f is strictly increasing in each argument, but nothing else". Few sentences later the author already claims "we know that f (x , y) = z implies x ≤ z and y ≤ z" and works with these premises. Again you either need to work out this yourself or consult external sources. And mental leaps like these happen again and again in all chapters I've read.
I think even little effort from the author like making explanatory comments, showing a picture/diagram or giving an example would turn this into a good book.
If you want to learn functional design I'd give this book a hard pass and look elsewhere. If you want to grind through this thing you need to code and think about every sentence carefully and maybe you can make it.
Let me describe the chapter 2 - Surpassing problem as an example.
At the beginning Bird outlines a function from which he wishes to derive a solution (so far so good).
But then out of the blue introduces "divide and conquer property of tails" that "we will need". Right off the bat it's impossible to derive the solution from first principles, because Bird already introduced deus ex machina code he uses to get his solution. How he came to the conclusion "we will need" this property we will never know.
From this property the author derives a 'join' function.
Unfortunately in multiple steps of the derivation he does "magical" code re-writes. One where he says he just does "operator distribution" but in fact
also changes another part of code substantially. In another Bird adds an unexpected substitution "ys = map fst (table ys)". These derivations feel "magical" because you have no idea why the author does them. You need to trace things from end to the beginning for them to make sense.
In another derivation Bird introduces dropWhile which assumes input of a function is
sorted, but this was very suprising to me. Only 2 sentences after dropWhile is introduced the author says input must be sorted and adds "sort". I learned something useful from this for the next chapters of the book - if you don't understand something keep reading!
Then there is a passage where he writes a new function that does a "reduction" from functions"2.2" and "2.3", but in fact there is nothing of value added except the use of variables from synonyms an also it's unclear what is being "reduced" since this new join definition is now 2x longer than the previous one ("2.2") and harder to read. This new join is also never used. Maybe there was some deeper thought but it's just lost on me.
At the end of the chapter the author says "... and tcount x tys = tcount x tys' by (2.1), ...", you of course go to 2.1 and you see "tcount z tys = length (dropWhile((z ≥) · fst) tys)" and you are like why are they equal? Is it because "tys" is sorted or because "≥" or some other explanation?
Ironically several parts of the chapter were dedicated to deriving and optimizing "tcount" function which at the end Bird shows we didn't need at all and could derive the computation by simple though process, all you needed was length of a list.
Another thing that adds to the frustration is that Bird also repeats some definitions, for example 'join' function in this chapter, but changes variable names so if you get used to 'z' meaning something in the next passage it is replaced by 'x'. Also sometimes he gives function definitions with function names and sometimes without.
Last point I'd like to make is that chapter 2 is only 4 pages long (yes four pages!) and it took me 2+ hours to read. If I would be given the test to implement the "Surpassing problem" on my own I could not replicate the solution from Birds book because multiple steps are not intuitive to me and the end solution does not resemble what the chapter was building up to (imho).
If I'd skip the whole chapter and just analyze and play with the solution presented at the end of the chapter in ghci I would get much more out of it than reading and re-reading the chapter.
The other chapters I've read are variations on chapter 2. For example in the next chapter which searches an inverse of "f (x , y) = z" it says "You can assume that f is strictly increasing in each argument, but nothing else". Few sentences later the author already claims "we know that f (x , y) = z implies x ≤ z and y ≤ z" and works with these premises. Again you either need to work out this yourself or consult external sources. And mental leaps like these happen again and again in all chapters I've read.
I think even little effort from the author like making explanatory comments, showing a picture/diagram or giving an example would turn this into a good book.
If you want to learn functional design I'd give this book a hard pass and look elsewhere. If you want to grind through this thing you need to code and think about every sentence carefully and maybe you can make it.
Want to read
August 26, 2024This entire review has been hidden because of spoilers.
March 12, 2012
Книга показалось слишком сложной для меня, возможно позже стоит сделать 2-й заход
Displaying 1 - 5 of 5 reviews