Most books on algorithm design are thoroughly imperative, sometimes with a thin veneer of object-oriented lacquer, to appeal to a larger audience. But it is slowly dawning on the computing community that these methods do not work so well on modern hardware, which is to say multiple cores under a variety of memory configurations. Functional programming, on the other hand, long a purely academic exercise in mathematical elegance, has fared much better.

But how does one learn the craft of designing functional algorithms? Up to now, the main source was Okasaki’s brilliant book [1]. Now, there is a second book, Richard Bird’s Pearls of functional algorithm design. It is just as brilliant, but in an entirely different way. Rather than focusing directly on particular algorithms, this book focuses on how to solve problems efficiently through functional algorithms.

Each of the book’s 30 chapters presents an interesting computational problem that needs to be solved. The problems can usually be specified in a fairly straightforward manner; in fact, most of the specifications can be turned into simple, but rather inefficient, functional code that “solves” the problem. Then comes design: the recognition of important invariants present in either the problem or the solution, which one can artfully exploit to provide a more efficient solution. Often, this design takes the form of a calculation. Thus, an “algebra of programming” emerges, codifying some of the craft of algorithm design into a more scientific methodology. This lets us glimpse even deeper structures that are present in problems, in their solutions, and in efficient algorithms for solving them.

Though the writing is crisp, and the explanations lucid, this is not an easy book to read. The difficulty lies in the density of the ideas presented. The rewards of persevering are definitely worth it, though. In fact, once immersed, I started to ponder other related questions: Which algorithms could be even further generalized? What would many of these algorithms look like if implemented in Coq or Agda? This is the effect that all good books have on me: well-presented and well-motivated material strives to become a stepping stone to further discovery.

Any serious computer scientist would benefit from reading and properly understanding this book.